백준 4179. 불! (python)

문제 : 백준 4179. 불!

백준의 BFS 문제이다. 사람과 불 두 가지에 대하여 bfs를 실행해야 한다.
문제를 접하고 살짝 해설을 보고 시작했었다.
오히려 살짝 해설을 본 게 문제 푸는데 내 생각과 맞지 않아 충돌이 생겨 오래 걸렸다.

다른 사람들의 풀이를 보면 불에 대한 bfs를 모두 실행하고 이동거리를 기록한 graph를 생성한 후에, 지훈이에 대한 bfs도 똑같이 실행을 하고 이동 거리에 대한 graph를 생성한다.
생성된 두 그래프의 가장자리 값이 지훈이가 더 적은 경우를 최단 거리로 탈출할 수 있는 경우로 보고 있다. 이해가 안된다면 다른 이들의 해설을 참조해보자.

하지만 나는 바보 같은 건지, 위 방법까지 생각을 못했던 건지 몰라도 지훈이가 이동하고, 불이 이동하고를 반복해서 풀이하고 싶었다.

무슨 말이냐면, 1분 즉 한 사이클씩 지훈이를 이동시키고, 그 다음 불을 이동시키고, 다시 지훈이를 이동시키면서 해결하려고 했다.
이 부분에 대해서 잘못 접근한 것은 불을 먼저 이동시켜야 한다는 것이었다. 왜냐면 지훈이가 이동한 곳에 불도 동시에 이동을 하게 되면 지훈이는 타죽으므로 이동할 수 없는 것이 맞다. 하지만 지훈이를 먼저 이동시키게 되면 이 경우가 배제되게 된다. 그래서 불을 먼저 이동시키고, 지훈이를 이동시키는 식으로 구현하였다.

최단 이동거리는 다른 bfs 문제 풀이에서 배운 것인데, 지훈이의 그래프를 지훈이의 위치 0을 제외한 다른 부분들은 -1로 초기값을 설정해두고 이동하는 곳으로 +1 씩 해주면서 최단거리를 갱신하는 방법이다.

'''
bfs 백준 4179. 불!

혜영이는 미로에서 일을 한다. 혜영이의 위치와 불의 위치를 감안해서
혜영이가 불에 타기 전에 미로에서 탈출할 수 있는 지의 여부, 그리고 얼마나 빨리 탈출할 수 있는 지를 결정해야한다.
미로의 가장자리에 접한 공간에서만 탈출할 수 있다.
혜영이와 불은 벽을 통과하지는 못한다.

입력
# : 벽
.: 지나갈 수 있는 공간
J : 혜영이의 미로에서 초기 위치(지나갈 수 있는 공간)
F : 불이 난 공간
4 4
####
#JF#
#..#
#..#

출력
혜영이가 불이 도달하기 전에 미로를 탈출할 수 없는 경우 IMPOSSIBLE을 출력한다.
혜영이가 미로에서 탈출할 수 있는 가장 빠른 시간을 출력한다.
3
'''
from collections import deque
r, c = map(int, input().split())  # 행, 열 입력
maze = [] # 사용자로부터 입력받는 미로 공간
for i in range(r):
    maze.append(list(input()))

j_queue = deque() #혜영이의 위치 지점 큐
f_queue = deque() #불난 지점 큐

fire_state = [[True] * c for _ in range(r)] #화재 상태 그래프 초기화
j_state = [[-1]*c for _ in range(r)] # 이동 상태 그래프 초기화

#시작점과 불난 지점 찾기 및 방문 그래프 초기화
for i in range(r):
    for j in range(c):
        if maze[i][j] == "J":  #J가 출발하는 곳의 화재 상태와 J상태 초기값 세팅
            j_queue.append((i, j))
            j_state[i][j] = 0
        elif maze[i][j] == "F":
            f_queue.append((i, j))
            fire_state[i][j] = False

# 이동 방향
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 혜영이의 움직이는 좌표를 큐에 넣는데, 더이상 움직일 곳이 없으면 반복을 종료한다.
def bfs():

    while j_queue:

        for _ in range(len(f_queue)):  #불이 발생한 곳들에 대한 bfs를 수행한다.
            x, y = f_queue.popleft()

            for i in range(4): # 불이 4방향으로 퍼지기 때문에 각 경우를 모두 처리한다.
                fx = x + dx[i]
                fy = y + dy[i]

                if fx < 0 or fx >= r or fy < 0 or fy >= c: # 이동한 불의 좌표가 그래프를 벗어났으면 다음 방향으로 넘어간다.
                    continue
                if maze[fx][fy] != "#" and fire_state[fx][fy]:
                    fire_state[fx][fy] = False
                    f_queue.append((fx, fy))

        for _ in range(len(j_queue)): #혜영이가 있는 곳들에 대한 bfs를 수행한다.
            x, y = j_queue.popleft()
            
            for i in range(4):
                jx = x + dx[i]
                jy = y + dy[i]

                if jx >= 0 and jx < r and jy >= 0 and jy < c:
                    if fire_state[jx][jy] and j_state[jx][jy] == -1 and maze[jx][jy] == ".": #해당 위치까지 거리보다 더 짧거나, 이동할 수 있는 곳이라면 최단거리를 갱신해준다.
                        j_state[jx][jy] = j_state[x][y] + 1
                        j_queue.append((jx, jy))
                if jx < 0 or jx >= r or jy < 0 or jy >= c:
                    return j_state[x][y]+1
    return "IMPOSSIBLE"

print(bfs())