[백준] 5427 불 python

www.acmicpc.net/problem/5427

5427번: 불

from collections import deque
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(q):
    man_move = 1
    while q:
        x, y, z = q.popleft()
        if z == 0 and (x == 0 or x == h - 1 or y == 0 or y == w - 1):
            return visit[x][y][0]
        if z == 0:
            man_move -= 1
        for i in range(4):
            dx = x + delta[i][0]
            dy = y + delta[i][1]
            if dx < 0 or dx >= h or dy < 0 or dy >= w: continue
            if building[dx][dy] == '#': continue
            if z:
                if visit[dx][dy][1] == -1: continue
                visit[dx][dy][1] = -1
                q.append((dx, dy, 1))
            else:
                if visit[dx][dy][1] == -1: continue
                if visit[dx][dy][0]: continue
                if dx == 0 or dx == h - 1 or dy == 0 or dy == w - 1:
                    return visit[x][y][0] + 1
                visit[dx][dy][0] = visit[x][y][0] + 1
                q.append((dx, dy, 0))
                man_move += 1
        if man_move == 0:
            break
    return "IMPOSSIBLE"

for tc in range(int(input())):
    w, h = map(int, input().split())
    building = []
    start = []
    fire = []
    visit = [[[0] * 2 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        tmp = input()
        building.append(tmp)
        for j in range(w):
            if tmp[j] == '*':
                fire.append((i, j, 1))
                visit[i][j][1] = -1
            elif tmp[j] == '@':
                start = (i, j, 0)
                visit[i][j][0] = 1
    q = deque()
    q.extend(fire) #불을 먼저 넣어서 진행
    q.append(start)

    print(bfs(q))

보기 편하게 continue 를 많이 사용했는데 알고리즘에는 별로 좋진 않은가보다.

pypy에서는 통과하였고 python에서는 통과하지 못하였다.

불인경우와 불이 아닌경우 모두 받아서 bfs를 돌려주면 된다.

bfs는 계속했으니 설명은 하지 않겠다.

man_move라고 한건 혹시나 사람이 움직이지 않는데 불만 계속 움직이면 시간이 소요되므로 break를 걸어주기위한 변수이다.

 

---

from collections import deque
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(q):
    while q:
        x, y = q.popleft()
        chk = -2 if visit[x][y] == -2 else visit[x][y]
        for i in range(4):
            dx = x + delta[i][0]
            dy = y + delta[i][1]
            if dx < 0 or dx >= h or dy < 0 or dy >= w:
                if chk != -2:
                    return visit[x][y] + 1
            else:
                if visit[dx][dy] == -1 and (building[dx][dy] == '.' or building[dx][dy] == '@'):
                    if chk == -2:
                        visit[dx][dy] = -2
                    else:
                        visit[dx][dy] = visit[x][y] + 1
                    q.append((dx, dy))

    return "IMPOSSIBLE"

for tc in range(int(input())):
    w, h = map(int, input().split())
    building = []
    start = []
    fire = []
    visit = [[-1] * w for _ in range(h)]
    for i in range(h):
        tmp = input()
        building.append(tmp)
        for j in range(w):
            if tmp[j] == '*':
                fire.append((i, j))
                visit[i][j] = -2
            elif tmp[j] == '@':
                start = (i, j)
                visit[i][j] = 0
    q = deque()
    q.extend(fire) #불을 먼저 넣어서 진행
    q.append(start)

    print(bfs(q))

타인의 코드에서 조금 고쳐서 만들었는데 훨씬 빠르다.

빌딩에서 탈출하면되므로 building array에서 범위를 벗어나는 경우에 return해주고, 벗어나지 않는경우에는 움직인다.

최소 거리를 구해야하므로 배열은 -1로 초기화를 해주었고 사람은 0 불은 -2로 초기화를 해주었다.

나머지는 일반적인 bfs와 비슷하다. 그리고 넘겨주는 값을 바로 print해준다.

---

쥬륵,,,