난이도
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
예제
입력 출력 4 4
####
#JF#
#..#
#..#3
풀이
예전에 풀다가 실패했던 문제이다.
3개월 전 싸피를 준비하다 못 풀었던 문제..
플레티넘 5 레벨의 백조의 호수 문제를 풀고, 이 문제를 풀어보니 어떻게 접근해야 하는지 알게 되었다.
우선, 불과 지훈이는 동시에 움직인다.
지훈이가 움직이려고 하는 곳에 불이 붙을 자리라면, 그 곳으로는 이동하지 않아야 한다.
이렇게 움직이다 탈출 지점을 만나면 움직인 횟수를 출력,
탈출 지점을 만나지 못한채 BFS가 끝나면 IMPOSSIBLE 을 출력한다.
지훈이의 위치를 가지고 BFS 를 진행하는데,
먼저 불을 이동 시키고, visited 배열을 업데이트 시킨다.
이러면 불이 다음에 붙을 곳은 지훈이가 이동하지 않게 된다.
그런 다음, 현재 큐에 들어있는 지훈이의 위치만큼 for 문을 돌린다. → 같은 횟수에서 움직일 수 있는 모든 곳을 탐색해야 한다.
이 과정을 반복하면서 탈출 지점을 찾고, 탈출 지점에 도착하지 못한 채 지훈이의 큐가 비게 되면 탈출을 못한 것이다.
코드
from sys import stdin
from collections import deque
input = stdin.readline
def solution():
R, C = map(int, input().split())
maze = list(list(input().rstrip()) for _ in range(R))
jihoon = ()
fires = deque()
for y in range(R):
for x in range(C):
if maze[y][x] == 'J':
jihoon = (y, x)
elif maze[y][x] == 'F':
fires.append((y, x))
visited = [[False for _ in range(C)] for _ in range(C)]
visited[jihoon[0]][jihoon[1]] = True
q = deque([jihoon])
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
ans = 0
while q:
fires_len = len(fires)
for i in range(fires_len):
fy, fx = fires.popleft()
visited[fy][fx] = True
for dx, dy in d:
nx, ny = fx + dx, fy + dy
if 0 <= nx < C and 0 <= ny < R and maze[ny][nx] != 'F' and maze[ny][nx] != '#':
maze[ny][nx] = 'F'
visited[ny][nx] = True
fires.append((ny, nx))
jihoon_len = len(q)
for i in range(jihoon_len):
sy, sx = q.popleft()
if sy == 0 or sy == R - 1 or sx == 0 or sx == C - 1 :
print(ans + 1)
return
for dx, dy in d:
nx, ny = sx + dx, sy + dy
if 0 <= nx < C and 0 <= ny < R and maze[ny][nx] != '#' and not visited[ny][nx]:
visited[ny][nx] = True
maze[ny][nx] = 'J'
q.append((ny, nx))
ans += 1
print("IMPOSSIBLE")
solution()
