문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
- 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
풀이
from collections import deque
import sys
input = sys.stdin.readline
r,c = map(int, input().split())
maze =[]
for _ in range(r):
maze.append(list(input().strip()))
fire_location=[]
# 사람의 위치와 불의 위치 파악
for x in range(c):
for y in range(r):
if maze[y][x] == 'J':
px,py = x,y
elif maze[y][x] == 'F':
fx,fy = x,y
fire_location.append((fx,fy))
# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def solve_problem():
global fire_location
visited_f = [[0]*c for _ in range(r)]
visited_j = [[0]*c for _ in range(r)]
person_q = deque()
fire_q = deque()
for x,y in fire_location:
fire_q.append([x,y])
visited_f[y][x] = 1
person_q.append((px, py))
visited_j[py][px] = 1
# 불에 대해서 먼저 기록
while fire_q:
prnx, prny = fire_q.popleft()
for i in range(4):
pnx = prnx + dx[i]
pny = prny + dy[i]
if (0<= pnx < c) and (0<= pny < r) and maze[pny][pnx]=='.' and not visited_f[pny][pnx]:
fire_q.append((pnx,pny))
visited_f[pny][pnx] = visited_f[prny][prnx] + 1
# 사람에 대해서 먼저 기록
while person_q:
prnx, prny = person_q.popleft()
if (prnx == 0) or (prnx == (c-1)) or (prny == 0) or (prny == (r-1)):
return visited_j[prny][prnx]
for i in range(4):
pnx = prnx + dx[i]
pny = prny + dy[i]
if (0<= pnx < c) and (0<= pny < r) and maze[pny][pnx]=='.' and not visited_j[pny][pnx]:
if (visited_f[pny][pnx] and visited_f[pny][pnx]>visited_j[prny][prnx]+1) or not visited_f[pny][pnx]:
person_q.append((pnx,pny))
visited_j[pny][pnx] = visited_j[prny][prnx] + 1
return False
result = solve_problem()
if result:
print(result)
else:
print('IMPOSSIBLE')해당 방법을 찾기까지 정말 오랜 시간이 걸린 거 같다. 물론 더 짧게 코딩할 수 있긴했지만, 그냥 빨리 풀고 싶은 마음이 컸으므로 어쩔 수 없긴 하다.
이 문제를 푸는 방법에서 가장 쉬운 방법은 불이 이동하는 시간과 사람이 움직이는 시간을 따로 따로 기록하는 것이다. 먼저 불이 이동한 시간을 기록한다. 그 후 불이 이동한 시간을 고려하여 사람이 이동하는 시간을 적고 나면 문제가 해결할 수 있다.
오답노트
from collections import deque
import sys
input = sys.stdin.readline
r,c = map(int, input().split())
maze =[]
for _ in range(r):
maze.append(list(input().strip()))
fire_location=[]
# 사람의 위치와 불의 위치 파악
for x in range(c):
for y in range(r):
if maze[y][x] == 'J':
px,py = x,y
elif maze[y][x] == 'F':
fx,fy = x,y
fire_location.append((fx,fy))
# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def solve_problem():
global fire_location
visited = [[0]*c for _ in range(r)]
for x,y in fire_location:
visited[y][x] = -1
person_q = deque()
person_q.append((px, py))
visited[py][px] = 1
while person_q:
# 그 외의 모든 불들이 확산됨.
fire_location_ex = []
for x,y in fire_location:
frnx , frny = x,y
for i in range(4):
fnx = frnx + dx[i]
fny = frny + dy[i]
if (0<= fnx < c) and (0<= fny < r) and maze[fny][fnx]=='.' and visited[fny][fnx] == 0:
fire_location_ex.append((fnx,fny))
visited[fny][fnx] = -1
# 확산된 불들이 다음에 더 넘어갈 수 있으므로 교체
fire_location= fire_location_ex
# 사람이 먼저 한 발짝 감.
prnx, prny = person_q.popleft()
if (prnx == 0) or (prnx == (c-1)) or (prny == 0) or (prny == (r-1)):
return visited[prny][prnx]
for i in range(4):
pnx = prnx + dx[i]
pny = prny + dy[i]
if (0<= pnx < c) and (0<= pny < r) and maze[pny][pnx]=='.' and visited[pny][pnx]==0:
person_q.append((pnx,pny))
visited[pny][pnx] = visited[prny][prnx] + 1
return False
result = solve_problem()
if result:
print(result)
else:
print('IMPOSSIBLE ')해당 코드에서 잘못된 부분은 사람이 움직일 수 있는 가능성을 고려할 때, 불은 확산되어 버린다는 점이다. 그렇기에 시간을 계산하는 것이 매우 어려워진다. 이 점을 생각해보면, 불과 사람의 이동시간을 따로따로 고려한다는 점이 정말 획시적인 아이디어 처럼 느껴졌다.
후기
- 이 문제는 어려운 점이 많이 느껴졌던 문제이다. 불은 여러개일 수 있다는 점과 같은 시간 동안 불과 사람을 고려해야 한다고 하니 여간 어려웠던 것이 아니다. 그래도 여러 방법을 찾아보고 생각해보니 문제가 풀린 거 같다. 덕분에 풀어서 속이 시원하다. 후후후
하나를 알고 그걸로 모든걸 관통한다.