[BaekJoon] 백준 4179번 : 불!

4179번 : 불!

지훈이는 불이 퍼진 곳에 이동 할 수 없다.

문제 설명이 부실해서 불의 이동 조건을 따지는데 조금 애매했다.

지훈이가 불에 타기 전에 탈출을 해야하니 불은 지훈이가 있는 곳에도 퍼질 수 있는지..

불이 먼저 퍼지는지.. 지훈이가 먼저 이동을 하는지..

우선 불이 지훈이가 있는 곳에도 퍼진다고 하면 주어진 예시는 답이 IMPOSSIBLE 이 나와야 한다.

그렇다면 결국 불은 지훈이가 있는 곳에는 갈 수 없고 불이 먼저 퍼진 뒤 지훈이가 이동한 것으로 하면 된다.

마지막으로 탈출 했는지 여부를 판단해야하기 때문에 현재 방문한 위치가 필드 가장자리이고 지훈이라면 걸린 시간을 출력한다.

---

import sys
from collections import deque


def solution():
    dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    character, fires = None, list()
    for i in range(N):
        for j in range(M):
            if field[i][j] == 'J':
                character = ('J', i, j, 0)
            elif field[i][j] == 'F':
                fires.append(('F', i, j, 0))

    visit = dict()
    queue = deque([])
    for fire in fires:
        visit[fire] = True
        queue.append(fire)
    visit[character] = True
    queue.append(character)

    while queue:
        who, now_i, now_j, time = queue.popleft()

        if now_i == 0 or now_i == N - 1 or now_j == 0 or now_j == M - 1:
            if who == 'J':
                return time + 1

        for value in dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < N and 0 <= visit_j < M and (who, visit_i, visit_j, time) not in visit:
                if who == 'F' and field[visit_i][visit_j] == '.':
                    field[visit_i][visit_j] = 'F'
                    visit[('F', visit_i, visit_j, time)] = True
                    queue.append(('F', visit_i, visit_j, time))
                elif who == 'J' and field[visit_i][visit_j] == '.':
                    field[visit_i][visit_j] = 'J'
                    visit[('J', visit_i, visit_j, time + 1)] = True
                    queue.append(('J', visit_i, visit_j, time + 1))

    return "IMPOSSIBLE"


if __name__ == "__main__":
    N, M = map(int, input().split())
    field = [list(sys.stdin.readline()) for _ in range(N)]

    print(solution())