문제 보러 가기
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
예제 입력 1
4 4
####
#JF#
#..#
#..#
예제 출력 1
3
처음에 나는 동시에 4방향으로 불을 번지게 하며 불이 번진곳은 벽으로 만들려고 하였다.
같은 while문안에 현재 한번 돌때 불은 동시에 번지고 지훈이는 상하좌우로 움직여보게 하려 하였으나
구현에 실패하였다. 그리고 인터넷에 검색하여 힌트를 얻고 다음과 같이 풀어보았다.
import sys
from collections import deque
input = sys.stdin.readline
dx=[-1,0,1,0]
dy=[0,1,0,-1]
if __name__=='__main__':
R,C = map(int, input().split()) # 행, 열
graph = []
QJ = deque() # 지훈이의 위치를 넣을 큐
QF = deque() # 불의 위치를 넣을 큐
measure_j = [[0] * C for _ in range(R)] # 지훈이가 위치할 곳의 시간을 기록할 행렬
measure_f = [[0] * C for _ in range(R)] # 불이 번지는 위치에 시간을 기록한다.
for i in range(R):
temp = list(input()) # 행 R별로 입력받는다.
for j in range(len(temp)): # 행과 열별로
if temp[j] == "J": # 지훈이가 있는 곳을 찾고
QJ.append((i, j)) # 지훈 큐에 넣고
measure_j[i][j] = 1 # 1을 기록해둔다
elif temp[j] == "F": # 불이 있는 곳을 찾고
QF.append((i, j)) # 불 큐에 넣고
measure_f[i][j] = 1 # 1을 기록한다.
graph.append(temp) # 미로의 구조를 저장한다
while QF: # 먼저 불부터 위치에 따른 번진 시간을 기록한다.
x,y = QF.popleft()
for i in range(4): # 상하좌우 사방으로
nx=x+dx[i]
ny=y+dy[i]
if 0 <= nx < R and 0 <= ny < C: # 미로안에서
if measure_f[nx][ny] == 0 and graph[nx][ny] != "#": # 불이 첫방문이거나 미로지도에서 벽이 아닌경우
measure_f[nx][ny] = measure_f[x][y] + 1 # 불 기록지에 1을 추가해서 상하좌우 번지게 함
QF.append((nx, ny))
while QJ:
x,y = QJ.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0 <= nx < R and 0 <= ny < C: # 미로안에서
if measure_j[nx][ny] == 0 and graph[nx][ny] != "#": # 지훈이 첫방문이거나 미로지도에서 벽이 아닌경우
if measure_f[nx][ny] == 0 or measure_f[nx][ny] > measure_j[x][y] + 1: # 불이 번지지 않았거나, 지훈이가 갈 위치의 걸린시간+1이 불이 난 시간보다 이르면
measure_j[nx][ny] = measure_j[x][y] + 1 # 지훈이는 그 위치로 이동할 수 있음
QJ.append((nx, ny))
else: # 미로를 벗어났다면
print(measure_j[x][y]) # 그때 시간 출력
sys.exit()
print("IMPOSSIBLE") # 벗어나지 못한다면 불가능 출력
