[Python] 4179. 불!

 

풀이

큐에 불을 모두 넣고 지훈이를 마지막에 append 하여 bfs 탐색

불은 벽이 아닌 것들을 모두 'F'로 바꾸고

지훈이는 visited 배열에 이동 거리를 누적해간다.

탈출구 (배열의 끝부분) 에 도달하면 탐색을 종료하고 이동 거리를 출력한다.

bfs가 끝났는데 탈출구에 도달하지 못했다면 IMPOSSIBLE을 출력한다.

 

코드

from collections import deque
import sys
input = sys.stdin.readline
r,c = map(int, input().split())
dx, dy = [0,1,0,-1], [1,0,-1,0]
visited = [[0]*c for _ in range(r)]
maze = [list(input().rstrip()) for _ in range(r)]
print(maze)
q = deque()
# 지훈이, 불 좌표 찾기
for i in range(r):
    for j in range(c):
        if maze[i][j] == 'J':
            x, y = i, j
        elif maze[i][j] == 'F':
            q.append((i,j,'F'))
# 지훈이를 마지막으로 넣음
if x == 0 or x == r-1 or y == 0 or y == c-1:
    print(1)
    exit()
q.append((x,y,'J'))
visited[x][y] = 1

check = 0
while q and not check:
    x, y, z = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] != '#' and maze[nx][ny] != 'F':
            # 탐색자가 불이면
            if z == 'F':
                # 불 번짐
                maze[nx][ny] = 'F'
                q.append((nx,ny,'F'))
            # 지훈이면 이동 수 누적
            elif z == 'J' and not visited[nx][ny]:
                # 탈출구에 도달하면 체크 표시하고 종료
                if nx == 0 or nx == r-1 or ny == 0 or ny == c-1:
                    visited[nx][ny] = visited[x][y] + 1
                    check = 1
                    break
                q.append((nx,ny,'J'))
                visited[nx][ny] = visited[x][y] + 1
if check:
    print(visited[nx][ny])
else:
    print('IMPOSSIBLE')