[백준 파이썬] 4179 불!

4179번: 불!

불이 퍼진 곳은 지훈이가 갈 수 없다. BFS로 먼저 불이 번지는 시간을 기록해두고, 불이 아에 번지지 않았거나 불이 아직 퍼지기 전이라면 지훈이를 이동시킨다.

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# 불 이동
def bfs_fire():
    q_F = deque(F)
    while q_F:
        x, y = q_F.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
			
            # 불이 퍼진 시각 기록
            if (0 <= nx < C and 0 <= ny < R
                and (visited_F[ny][nx] == -1
                     or visited_F[ny][nx] > visited_F[y][x]+1)
                and maze[ny][nx] != '#'):

                q_F.append([nx, ny])
                visited_F[ny][nx] = visited_F[y][x] + 1

# 지훈 이동
def bfs_jihoon():
    q_J = deque([J])

    while q_J:
        x, y = q_J.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 지훈이가 방문하는 시각 기록
            if (0 <= nx < C and 0 <= ny < R
                and visited_J[ny][nx] == -1
                and maze[ny][nx] == '.'
                and (visited_F[ny][nx] > visited_J[y][x]+1 # 불보다 먼저 도달했거나
                     or visited_F[ny][nx] == -1)):         # 불이 닿지 않은 영역
                visited_J[ny][nx] = visited_J[y][x] + 1
                q_J.append([nx, ny])

                # 가장자리에 도달했다면 탈출
                if (nx == 0 
                    or ny == 0 
                    or nx == C-1 
                    or ny == R-1):
                    return visited_J[ny][nx] + 1
                
    return 'IMPOSSIBLE'


R, C = map(int, input().split())
maze = [list(input()) for _ in range(R)]


J = [0, 0]
F = []
for i in range(R):
    for j in range(C):
        if maze[i][j] == 'J':
            J = [j, i]
        if maze[i][j] == 'F':
            F.append([j, i])

visited_J = [[-1 for _ in range(C)] for _ in range(R)]
visited_F = [[-1 for _ in range(C)] for _ in range(R)]

# 지훈이랑 불 시작 위치 기록
visited_J[J[1]][J[0]] = 0
for f_x, f_y in F:
    visited_F[f_y][f_x] = 0

# 처음부터 가장자리라면 바로 탈출
if (J[0] == 0 or J[0] == C-1
    or J[1] == 0 or J[1] == R-1):
    print(1)
else:
    bfs_fire()
    print(bfs_jihoon())