문제
접근
2차원 공간에서 최단 경로를 찾아야 한다.
특이한 점은 불이라는 존재이다.
상근이가 1초마다 한 칸을 움직일 수 있듯이 불도 1초마다 인접한 칸으로 전파된다.
매 초 불길이 전파되고, 이러한 불에 닿지 않고 출구까지 가는 방법을 찾아야 한다.
상근이와 불을 동시에 생각하지 않으면 쉬워질 것 같다.
우선 불에 대해서 BFS를 수행하며 불이 전파되는 칸마다 몇 초에 전파 되었는지 기록해주자.
예를 들어 다음과 같은 공간이라고 하자.
F는 불의 초기 위치이다.
F 0 0 0
0 0 0 0
0 0 0 0
이 때 불의 전파를 기록한다면 다음과 같은 식일 것이다.
F 1 2 3
1 2 3 4
2 3 4 5
불이 여러개일 경우는 해당 칸에 가장 빨리 도달한 시간을 기록하면 된다.
이 방법으로 풀었더니 시간 초과가 떳다.
아마 판의 크기가 크기 때문에, 모든 불에 대해서 BFS를 수행하는데 시간이 오래걸리는 것 같다.
아무래도 사람과 불을 함께 움직여줘야 할 것 같다.
불에 대해 모두 구해놓고 시작하는 것이 아니라, 1초단위로 불을 움직이고, 사람을 움직이는 식으로 진행하면 되지 않을까
맞았다.
1초 단위로 불->사람->불->사람. … 을 움직이면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from collections import deque
import sys
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def fireBFS():
fireSize = len(fireQ)
while fireSize:
nowx, nowy = fireQ.popleft()
for x, y in zip(dx,dy):
nx = x+nowx
ny = y+nowy
if nx < 0 or nx >= w or ny < 0 or ny >= h or board[ny][nx] == -1:
continue
if board[ny][nx] == 0:
board[ny][nx] = board[nowy][nowx] + 1
fireQ.append((nx,ny))
fireSize -= 1
def personBFS(start):
q = deque()
q.append(start)
visit[start[1]][start[0]] = 1
while q:
qSize = len(q)
while qSize:
nowx, nowy = q.popleft()
if nowx == 0 or nowx == w-1 or nowy == 0 or nowy == h-1:
return visit[nowy][nowx]
for x, y in zip(dx,dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= w or ny < 0 or ny >= h or board[ny][nx] == -1:
continue
if board[ny][nx] == 0 and visit[ny][nx] == 0:
visit[ny][nx] = visit[nowy][nowx] + 1
q.append((nx,ny))
qSize -= 1
fireBFS()
return 'IMPOSSIBLE'
T = int(input())
for _ in range(T):
w, h = map(int,sys.stdin.readline().split(' '))
board = [[0] * (w) for _ in range(h)]
visit = [[0] * (w) for _ in range(h)]
fireQ = deque()
# input board create
# -1 : 벽
# 0 : 이동 가능
# 1 : 불
for i in range(h):
item = sys.stdin.readline()
for j in range(w):
if item[j] == '#':
board[i][j] = -1
elif item[j] == '*':
board[i][j] = 1
fireQ.append((j,i))
elif item[j] == '.':
board[i][j] = 0
else:
board[i][j] = 0
start = (j,i)
fireBFS()
ans = personBFS(start)
print(ans)