백준 5427 불 (파이썬)

풀이

from collections import deque

# 불이 퍼지는 함수 시간 단위로 한번만 실행됨
def bfs1():
    for _ in range(len(Q_f)):
        r, c = Q_f.popleft()
        for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nr, nc = r + di, c + dj
            if 0 <= nr < N and 0 <= nc < M:
                if arr[nr][nc] == '.' or arr[nr][nc] == '@':
                    arr[nr][nc] = '*'
                    Q_f.append((nr, nc))

# 움직이는 함수, 갈수 있는 방향에서 한번 움직이고 불 함수를 호출
# 불 - 이동 - 불 - 이동 순서
def bfs2(r, c):
    visited[r][c] = 1
    while Q_p:
        for _ in range(len(Q_p)):
            r, c = Q_p.popleft()
            for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                nr, nc = r + di, c + dj
                if not (0 <= nr < N and 0 <= nc < M):
                    return visited[r][c]
                if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == 0 and arr[nr][nc] == '.':
                    visited[nr][nc] = visited[r][c] + 1
                    Q_p.append((nr, nc))
        bfs1()
    return 'IMPOSSIBLE'

for tc in range(int(input())):
    M, N = map(int, input().split())
    arr = [list(input()) for _ in range(N)]
    Q_f = deque()
    Q_p = deque()
    visited = [[0]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if arr[i][j] == '@':
                Q_p.append((i, j))
            elif arr[i][j] == '*':
                Q_f.append((i, j))

    bfs1()
    r, c = Q_p[0]
    print(bfs2(r, c))

 

---

후기 및 해설

• 처음에 잘못 접근해서 한참 헤맸다.
• visited를 불, 사람 두 개를 만들어주고 사람이 움직일 수 있는 조건을 이 두 visited의 값을 비교하며 해줬다.
• 그런데 이 방법은 비효율적이고 복잡하다. 결국 이 방법은 불을 다 이동시키고, 사람을 이동시키는 건데, 
• 이렇게 하면 시간 초과가 뜬다.
• 불 -> 사람 -> 불 -> 사람의 순서로 해야 한다는 생각이 들어 구현해보았다.
• 일단, visited불을 없애주고 사람이 움직일 때 표시하는 것으로 한 개만 만들었다.
• 처음 불이 이동하는 함수가 돌아간다.
• 미리 Q-f에 넣어둔 개수만큼 불이 옮겨 붙는다.
• 다음, 사람이 이동하는 함수를 만들었다.
• 이 함수는 내부에서 불 함수를 호출하여 순서대로 움직이게 해 준다.
• 지금 와서 보면 간단한데.. 코드를 짤 때는 너무 복잡하고 어렵다..