[Python/파이썬] 백준 4179번 불!

4179번: 불!

 

문제

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

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

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

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

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

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

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

코드

from collections import deque

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

r, c = map(int, input().rstrip().split())
maze = []
q = deque([])
for i in range(r):
    maze.append(list(input())) # #은 벽, .은 빈 공간, J는 지훈이 초기 위치, F는 불
    for j in range(c):
        if maze[i][j] == 'J':
            q.appendleft((i, j, 0, False))
        elif maze[i][j] == 'F':
            q.append((i, j, 0, True))

while q:
    x, y, t, is_fire = q.popleft()
    if (x == 0 or x == r-1 or y == 0 or y == c-1) and maze[x][y] != 'F' and not is_fire:    # 탈출
        print(t+1)
        exit()
    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] != '#':
            if maze[nx][ny] == '.' and not is_fire: # 지훈이
                q.append((nx, ny, t+1, False))
                maze[nx][ny] = 'V'
            elif is_fire and maze[nx][ny] != 'F':   # 불 확산
                maze[nx][ny] = 'F'
                q.append((nx, ny, t+1, True))
    
print("IMPOSSIBLE")