import sys
from collections import deque
def solution(miro):
time = 0
delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
j_visited = [[False] * c for _ in range(r)]
j_q = deque()
fire_q = deque()
for i in range(r):
for j in range(c):
if miro[i][j] == 'J':
miro[i][j] = '.'
j_q.append((i, j))
elif miro[i][j] == 'F':
fire_q.append((i, j))
while j_q: # 지훈이가 갈 곳이 있다면
for _ in range(len(fire_q)): # 먼저 불 확산.
row, col = fire_q.popleft()
for i in range(4):
delta_row, delta_col = delta[i]
new_row = row + delta_row
new_col = col + delta_col
if new_row < 0 or new_row >= r or new_col < 0 or new_col >= c:
continue
if miro[new_row][new_col] == '.':
miro[new_row][new_col] = 'F'
fire_q.append((new_row, new_col))
for _ in range(len(j_q)): # BFS로 지훈이가 다음 타임에 갈 방향 탐색.
row, col = j_q.popleft()
for i in range(4):
delta_row, delta_col = delta[i]
new_row = row + delta_row
new_col = col + delta_col
if new_row < 0 or new_row >= r or new_col < 0 or new_col >= c: # 경계 지점에 있으면 다음 타임에 탈출 확정.
return time + 1
if not j_visited[new_row][new_col] and miro[new_row][new_col] == '.':
j_visited[new_row][new_col] = True
j_q.append((new_row, new_col))
time += 1
# 갈 곳이 더이상 없다면
return "IMPOSSIBLE"
r, c = map(int, sys.stdin.readline().split())
miro = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
print(solution(miro))
문제 정의
2차원 격자의 미로에서 지훈이와 불이 1초마다 1칸씩 상하좌우로 움직일 때
지훈이가 불을 피해 탈출할 수 있는 최단거리를 구하는 문제이다.
시간 복잡도 계산
최단거리 문제이기 때문에 BFS 탐색을 떠올렸으며
최악의 경우 BFS러 전부 탐색할 경우 시간초과가 나지 않을 지 확인해야한다.
행과 열의 개수가 각각 최대 1,000이기 때문에 전체 탐색 범위는
최대 1,000,000이므로 최악의 경우에도 시간초과가 나지 않을것이라 판단했다.
문제 풀이
먼저 불을 퍼트려서 갈 수 있는 길들을 비활성화 시키고
지훈이는 ' . '인 곳만 가도록 BFS로 구현했다.
이렇게 구현해도 문제 없는 이유는 불 기준으로 상하좌우에 있는 길들은
지훈이가 먼저 이동한다 생각해도 다음턴에 불에 바로 삼켜지기 때문이다.
ps. (처음엔 지훈이가 움직이는 BFS와 불이 움직이는 BFS를 함수로 따로 구현하려 시도했다. 하지만 각각 한 Breadth씩 순서대로 나가야 하기 때문에 하나의 함수에 구현하게 되었다.)
예외 사항
F가 시작 지점이 여러 개일 수도 있다.