BOJ 5427 불
접근 방법
불이 지나간 자리나 불과 겹칠 자리는 사람이 지나가지 못하므로 불이 각 칸에 도달하는 최소 시간을 기록한 뒤에 이 시간을 바탕으로 사람이 탈출 지점에 도달할 수 있는지 판단하고자 하였다.
이때 문제를 너무 복잡하게 풀었다. 메모리에 여유가 있음에도 굳이 set를 사용하거나 하나의 2차원 배열로 문제를 해결하려고 하였다.
정답 코드 (Pypy 3864ms)
import sys
from collections import deque
input = sys.stdin.readline
"""
불로 먼저 bfs해서 각 칸에 도달하는 시간 기록
그 다음 사람이 불보다 먼저 도착하는 칸 + 벽이 아닌 공간에만 도달할 수 있게 bfs
"""
moves = [(1,0),(-1,0),(0,1),(0,-1)]
T = int(input())
for _ in range(T):
w,h = map(int, input().split())
maps = []
for _ in range(h):
maps.append(list(input().rstrip()))
# 탈출 위치 + 불, 사람 시작 위치
ends = set() # 탈출 가능 위치들을 저장
fires = [] # 불 시작 위치 저장
start_h, start_w = 0,0
start_t = 0
for i in range(h):
for j in range(w):
# 모서리에 있는 .인 곳들 = 탈출 위치
if maps[i][j]=='.' and (i == h-1 or j == w-1 or i == 0 or j == 0):
ends.add((i,j))
elif maps[i][j] == '@':
start_h, start_w = i,j
elif maps[i][j] == '*':
fires.append((i,j))
#불 시작 지점은 불 도달 시간을 0으로
maps[i][j] = 1
# 처음부터 탈출 지점에 있는지 확인
if start_h == h-1 or start_h==0 or start_w == w-1 or start_w == 0:
print(1)
continue
# 불 먼저 bfs해서 각 가능한 칸에 도달하는 최소 시간 기록
q = deque(fires)
while q:
fire_h, fire_w = q.popleft()
for dh, dw in moves:
new_h, new_w = fire_h+dh, fire_w+dw
if 0<=new_h<h and 0<=new_w<w and maps[new_h][new_w]!="#":
#빈 곳이라면
if maps[new_h][new_w] == '.':
#이전 불 위치보다 1 증가
maps[new_h][new_w] = maps[fire_h][fire_w]+1
q.append((new_h, new_w))
#사람 bfs
q = deque([(start_h, start_w, 1)])
visited = set()
found = False
while q:
cur_h, cur_w,t = q.popleft()
#탈출 지점에 도착했다면
if (cur_h, cur_w) in ends:
print(t)
found = True
break
for dh, dw in moves:
new_h, new_w = cur_h + dh, cur_w + dw
if 0<=new_h<h and 0<=new_w<w and maps[new_h][new_w]!="#" and (new_h, new_w) not in visited:
#사람이 도달하는 시간이 불 도달 시간보다 빠르다면 이동
if isinstance(maps[new_h][new_w], int) and maps[new_h][new_w] > t+1:
q.append((new_h, new_w,t+1))
elif maps[new_h][new_w] == '.':
q.append((new_h, new_w, t+1))
visited.add((new_h, new_w))
if not found:
print("IMPOSSIBLE")
푸는 과정은 어느 정도 맞았지만, list 안에 문자열을 저장했다가 숫자를 저장하는 과정에서 오류가 발생할 경우가 높고, 그 오류를 해결하기 위해 isinstance을 사용했는데 이 과정에서 시간초과가 났다.
이 풀이 코드에서 생기는 문제점은 불이 각 칸에 도달한 시간을 굳이 maps 안에 저장해서 풀려고 했던 것 같다.
더 효율적인 코드 (Python 3684ms)
불과 사람이 도달하는 시간들을 따로 저장해서 더 간단하게 풀었다.ㅎ
import sys
from collections import deque
input = sys.stdin.readline
"""
불로 먼저 bfs해서 각 칸에 도달하는 시간 기록
그 다음 사람이 불보다 먼저 도착하는 칸 + 벽이 아닌 공간에만 도달할 수 있게 bfs
"""
moves = [(1,0),(-1,0),(0,1),(0,-1)]
T = int(input())
for _ in range(T):
w,h = map(int, input().split())
maps = []
for _ in range(h):
maps.append(list(input().rstrip()))
# 불, 사람 시작 위치
fires = []
start_h, start_w = 0,0
fire_t = [[-1]*w for _ in range(h)]
person_t = [[-1]*w for _ in range(h)]
for i in range(h):
for j in range(w):
if maps[i][j] == '@':
start_h, start_w = i,j
person_t[start_h][start_w] = 1
elif maps[i][j] == '*':
fires.append((i,j))
fire_t[i][j] = 1
# 불 먼저 bfs해서 각 가능한 칸에 도달하는 최소 시간 기록
q = deque(fires)
while q:
fire_h, fire_w = q.popleft()
for dh, dw in moves:
new_h, new_w = fire_h+dh, fire_w+dw
if 0<=new_h<h and 0<=new_w<w and maps[new_h][new_w]!="#":
#빈 곳이라면
if (maps[new_h][new_w] == '.' or maps[new_h][new_w] == '@') and fire_t[new_h][new_w] == -1:
#이전 불 위치보다 1 증가
fire_t[new_h][new_w] = fire_t[fire_h][fire_w] + 1
q.append((new_h, new_w))
#사람 bfs
q = deque([(start_h, start_w)])
found = False
while q:
cur_h, cur_w = q.popleft()
#탈출 지점에 도착했다면
if cur_h==h-1 or cur_h==0 or cur_w == 0 or cur_w == w-1:
found = True
print(person_t[cur_h][cur_w])
break
for dh, dw in moves:
new_h, new_w = cur_h + dh, cur_w + dw
if 0<=new_h<h and 0<=new_w<w and maps[new_h][new_w]!="#" and person_t[new_h][new_w] == -1:
#사람이 도달하는 시간이 불 도달 시간보다 빠르다면 이동
if fire_t[new_h][new_w] == -1 or fire_t[new_h][new_w] > person_t[cur_h][cur_w]+1:
q.append((new_h, new_w))
person_t[new_h][new_w] = person_t[cur_h][cur_w]+1
if not found:
print("IMPOSSIBLE")