오늘의 알고리즘 boj- 4179

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

풀이

우선 지훈이와 불을 구분하여 queue에 담아준다. 그런 다음 지훈이가 _type을 통해서 지훈이가 이동한 것으로 확인이 되고 미로 끝에 닿았다면 지훈이는 탈출에 성공한 것이므로 거리값을 리턴해준다.

불이 이동한 것도 지훈이가 이동한 것도 다 기존 bfs처럼 방문처리를 해버리면 이동불가한 지역처럼 처리가 되기 때문에 아래 코드와 같이 기존 bfs구문처럼 방문처리된 곳, 벽, 바깥으로 벗어난 부분을 continue처리해주어 queue에 담기지 않도록 했다.

마지막으로 큐에 값이 없고 더이상 진행이 안되면 실패했다는 표시로 -1을 리턴해주었다. (impossible을 리턴하여 바로 프린트하는 방법도 있지만 리턴값이 int라 이런식으로 처리했다.)

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
maze = [input() for _ in range(N)]
directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
visited = [[0] * M for _ in range(N)]
JIHOON = 0
FIRE = 1

route_queue = deque()
for i in range(N):
    for j in range(M):
        if maze[i][j] == "J":
            jihoon_location= (i, j, JIHOON)
            visited[i][j] = 1
        elif maze[i][j] == "F":
            route_queue.append((i, j, FIRE))
            visited[i][j] = 1

route_queue.append(jihoon_location)

def check_jihoon_trail() -> int:
    while route_queue:
        cur_row, cur_col, _type = route_queue.popleft()

        if _type == JIHOON and (cur_row == 0 or cur_row == N-1 or cur_col == 0 or cur_col == M-1):
            return visited[cur_row][cur_col]
        
        for direction in directions:
            next_row = cur_row + direction[0]
            next_col = cur_col + direction[1]

            if 0 > next_row or next_row >= N or 0 > next_col or next_col >= M: continue

            if maze[next_row][next_col] == "#": continue

            if visited[next_row][next_col]: continue

            visited[next_row][next_col] = visited[cur_row][cur_col] +1
            route_queue.append((next_row, next_col, _type))
    return -1


result = check_jihoon_trail()

print(result if result != -1 else "IMPOSSIBLE")