📌 문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
예제 입력 1
4 4
####
#JF#
#..#
#..#예제 출력 1
3📌 풀이
💬 Code
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(input().rstrip()))
if 'J' in graph[i]:
q = deque([(0, i, graph[i].index('J'))])
for i in range(n):
for j in range(m):
if graph[i][j] == 'F':
q.append((-1, i, j))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = 'IMPOSSIBLE'
while q:
time, x, y = q.popleft()
# 지훈이 탈출
if time > -1 and graph[x][y] != 'F' and (x == 0 or y == 0 or x == n - 1 or y == m - 1):
ans = time + 1
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != '#':
# 지훈이 이동
if time > -1 and graph[nx][ny] == '.':
graph[nx][ny] = '_'
q.append((time + 1, nx, ny))
# 불 퍼뜨리기
elif time == -1 and graph[nx][ny] != 'F':
graph[nx][ny] = 'F'
q.append((-1, nx, ny))
print(ans)💡 Solution
이동하는 대상인 지훈이(J)와 불(F)의 위치를 큐에 넣고 BFS를 진행한다. 그리고 지훈이의 탈출 시간을 출력해야 하므로 큐에는 위치와 함께 시간 정보도 넣어준다. (불의 시간은 고려 대상 X → -1로 넣어줌)
또, 주어진 예제만 봐도 한 타임에 지훈이가 불보다 먼저 이동해야 하는 건 쉽게 캐치할 수 있다.
그럼 같은 큐에 들어가는 지훈이와 불의 이동 순서를 어떻게 정해줄 수 있을까? 처음엔 우선순위 큐를 써야 하나 싶었다. 근데 조금만 생각해보니 가장 처음에 지훈이를 큐에 넣어주기만 하면 이후 타임에 계속 지훈이가 먼저 이동하게 되는 것을 알 수 있었다.
이렇게! 그래서 아예 미로 입력을 받을 때 지훈이를 찾아서 큐에 넣어주고, 입력이 끝나면 불들(J는 입력에서 하나만 주어진다.는 조건은 있었지만 F는 없었기 때문에 불이 여러 군데 있을 거라는 사실을 캐치해야 한다.)을 찾아서 큐에 넣어준다.
이제 이동!
-
지훈이 이동
1) 지훈이가 왔던 길을 되돌아가지 않도록 특정 위치의 방문 여부를 체크해두어야 하는데, visited 리스트를 사용하는 대신 방문 가능한 곳의 값을_로 바꿔주었다.
2) 여기서 지훈이를 바로 탈출시키지 않는 이유는, 아직 한 타임이 끝나지 않았기 때문이다. 한 타임 안에서 지훈이의 이동을 먼저 처리해주기 때문에, 지훈이가 방문하려는 곳이 이어서 불의 이동으로 인해 불로 덮일 수 있으므로! 한 타임의 이동이 모두 끝난 후 탈출시켜야 한다. -
불 퍼뜨리기
불 자리에 또 불을 퍼뜨리면서 일을 2번 할 필요가 없기 때문에 graph[nx][ny] != 'F' 조건을 달아주고 불을 퍼뜨린다.
마지막으로 지훈이를 탈출시켜준다.
지훈이가 이동한 위치가 불로 덮이지 않았고 (graph[x][y] != 'F'), 모서리라면(x == 0 or y == 0 or x == n - 1 or y == m - 1) 답을 갱신! 처음에 예제만 생각하고 x==0, y==0 조건을 넣지 않아서 틀렸었음 😅 히든테케 잘 생각하고 제출하기,,
숏코딩 랭킹에 들었다..🤭
