문제 링크
문제 설명
R*C 크기의 미로가 주어진다. 미로의 각 칸은 빈칸이거나 지훈이가 위치하거나 불이 위치하거나 벽이 위치한다. 지훈이는 매초 수평/수직 방향으로 이동이 가능하고, 불은 매초마다 네 방향으로 확산된다. 지훈이가 불에 타기 전에 탈출이 가능한지, 가능하다면 얼마나 빨리 탈출 가능한지 구하시오 !
문제 풀이
시도 1
i초에 불이 확산된 위치를 알아야한다. maze에 직접 값을 조작하면 복잡해질 것같아서 fire 리스트를 만들어서 불의 좌표를 저장했다.
fire[i]: i초 뒤에 확산된 불의 좌표들 저장
bfs를 돌면서 t초에서의 지훈이의 이동을 수행하는데
- 우선 불을 확산시킨다 (t+1초의 결과)
- 지훈이가 이동가능한 네 방향중 벽이 아니고, 불이 확산되지 않은 칸을 queue에 넣어준다.
근데 7%에서 시간초과가 났다 ^_ㅠ,,
import sys
from collections import deque
import copy
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
R, C = map(int, input().split())
maze = []
jihoon = []
fire = [[]]
for i in range(R):
tmp = list(input().strip())
for j in range(C):
if tmp[j] == 'J':
jihoon = [i,j]
tmp[j] = '.'
elif tmp[j] == 'F':
fire[0].append((i,j))
tmp[j] = '.'
maze.append(tmp)
def in_range(x, y):
if x in range(R) and y in range(C):
return True
return False
def move_fire():
tmp = set()
for x, y in fire[-1]:
for i in range(4):
fx, fy = x+dx[i], y+dy[i]
if in_range(fx, fy) and maze[fx][fy] != '#':
tmp.add((fx, fy))
tmp.add((x, y))
fire.append(list(tmp))
def bfs(x, y):
queue = deque([[x, y, 0]])
visited = [[0]*C for _ in range(R)]
visited[x][y] = 1
while queue:
x, y, time = queue.popleft()
if x == 0 or x == R-1 or y == 0 or y == C-1:
return time+1
if len(fire) == time+1:
move_fire()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny) and visited[nx][ny] == 0 and maze[nx][ny] == '.' and (nx, ny) not in fire[time+1]:
queue.append([nx, ny, time+1])
visited[nx][ny] = 1
return -1
answer = bfs(jihoon[0], jihoon[1])
if answer == -1:
print("IMPOSSIBLE")
else:
print(answer)
시도 2
불queue와 지훈이queue를 만들어서 bfs를 각각에 대해서 돌려준다.
while문의 기준을 지훈이로 잡고,
- 불을 확산시킨다
- 지훈이를 이동시킨다.
-> 네방향중 빈칸에 있으면 queue에 넣어준다.
이동시의 for문을 for _ in range(len(jihoon)): 로 돌리면 t초에서의 이동만 계산되므로 따로 시간을 저장할 필요가 없다 .
def bfs():
time = 0
while jihoon:
#불 확산시키기
for _ in range(len(fire)):
x, y = fire.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny) and (maze[nx][ny] == '.' or maze[nx][ny] == 'J') :
maze[nx][ny] = 'F'
fire.append((nx,ny))
#지훈이 이동
for _ in range(len(jihoon)):
x, y = jihoon.popleft()
if x == 0 or x == R-1 or y == 0 or y == C-1:
return time+1
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny) and maze[nx][ny] == '.':
maze[nx][ny] = 'J'
jihoon.append((nx, ny))
time += 1
return -1전체 코드
import sys
from collections import deque
import copy
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
R, C = map(int, input().split())
maze = []
jihoon = deque()
fire = deque()
for i in range(R):
tmp = list(input().strip())
for j in range(C):
if tmp[j] == 'J':
jihoon.append((i,j))
elif tmp[j] == 'F':
fire.append((i,j))
maze.append(tmp)
def in_range(x, y):
if x in range(R) and y in range(C):
return True
return False
# fire[i] : i초 뒤 불의 확산좌표들 저장
def move_fire():
tmp = set()
for x, y in fire[-1]:
for i in range(4):
fx, fy = x+dx[i], y+dy[i]
if in_range(fx, fy) and maze[fx][fy] != '#':
tmp.add((fx, fy))
tmp.add((x, y))
fire.append(list(tmp))
def bfs():
time = 0
while jihoon:
#불 확산시키기
for _ in range(len(fire)):
x, y = fire.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny) and (maze[nx][ny] == '.' or maze[nx][ny] == 'J') :
maze[nx][ny] = 'F'
fire.append((nx,ny))
#지훈이 이동
for _ in range(len(jihoon)):
x, y = jihoon.popleft()
if x == 0 or x == R-1 or y == 0 or y == C-1:
return time+1
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny) and maze[nx][ny] == '.':
maze[nx][ny] = 'J'
jihoon.append((nx, ny))
time += 1
return -1
answer = bfs()
if answer == -1:
print("IMPOSSIBLE")
else:
print(answer)
느낀점
그동안 bfs를 이용한 문제는 내가 정한 템플릿에 끼워맞춰서 풀었는데 문제에 따라 유동적으로 변경해서 풀 수 있어야될 것 같다. ,,,, 이렇게 큐를 두개 만든다던가,,, 시간을 저장하지 않고 해당 시간내의 가능한 이동을 한번에 처리한다던가 ,,
어렵꾼
Hongik CE