🔥 불!
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
예제 입력 1
4 4
####
#JF#
#..#
#..#예제 출력 1
3📖 알고리즘
문제에서 묻고자 하는 것은 미로에서 지훈이가 가장자리로 얼마나 빨리 도달할 수 있는지이다.
다시 말해, Weight가 없는 그래프가 주어지고 [특정 노드에서 특정 노드의 최단거리] 문제로 치환할 수 있다.
따라서 우리는 쉽게 BFS를 떠올릴 수 있다. 다만, 주의할 점은 지훈이 뿐만 아니라 불의 이동도 동시에 고려해주어야 한다는 점이다.
📐 설계
TRY 1, 시간 초과
지훈이와 불로부터 BFS를 출발하여 시간을 증가시켜준다. 그렇게 모든 BFS 탐색을 끝마치고 가장자리에 위치하며 벽과 불을 제외한 시간들 중에서 제일 작은 숫자를 뽑아서 출력한다. 이 때, 탈출하기 위한 마지막 1분도 포함되어 있으니 +1분을 해준다.
TRY 2, 메모리 초과
1트에서는 BFS 탐색 전부 끝마치고 시간을 찾았는데 2트에서는 while문 중간에 지훈이가 가장자리에 도달했을 경우 바로 탈출할 수 있도록 수정하였다.
# 지훈이 탈출 조건
if (x == 0 or x == R-1 or y == 0 or y == C-1) and who == 'J':
return count[x][y] + 1TRY 3, 정답
솔루션 참고: https://velog.io/@hygge/Python-백준-4179-불-BFS
메모리 초과가 나서 최대한 변수 사용을 줄였다. 아래는 2트에서 삭제한 변수들이다.
나름 줄인다고 줄였는데 더 이상 뭘 더 줄여야할지 몰라서 솔루션을 참고하였다. 😡
- 방문 여부 visited 배열
- 불과 지훈이를 판별하는 who
- 시간을 기록하는 time 배열
- 불의 위치를 담는 fire 배열
최대한 Queue 하나로 전부 해결할 수 있도록 하였다.
👨🏻💻 CODE
TRY 1
import sys
input = sys.stdin.readline
from collections import deque
R,C = map(int,input().split())
maze = [] # 그래프
dx = [1,-1,0,0]
dy = [0,0,1,-1]
fire = [] # 불 위치
edge = [] # 가장자리
for i in range(R):
maze.append(list(input().rstrip()))
# 지훈,불 위치 찾기
for i in range(R):
for j in range(C):
if maze[i][j] == 'J':
j_x,j_y = (i,j)
if maze[i][j] == 'F':
fire.append((i,j))
# 최단 거리 찾기
def bfs(a,b):
q = deque([])
q.append([(a,b),'J'])
for i in range(len(fire)):
q.append([(fire[i][0],fire[i][1]),'F'])
visited = [[False]*C for _ in range(R)]
count = [[0]*C for _ in range(R)]
while q:
temp = q.popleft()
x,y = temp[0]
who = temp[1]
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<R and 0<=ny<C and visited[nx][ny] == False and (nx,ny) not in fire:
if maze[nx][ny] == '.':
if who == 'J':
q.append([(nx,ny),'J'])
visited[nx][ny] = True
count[nx][ny] = count[x][y] + 1
if who == 'F':
q.append([(nx,ny),'F'])
fire.append((nx,ny))
return count
distance = bfs(j_x,j_y)
answer = []
# 가장자리 최단거리
for i in range(R):
if i == 0 or i == R-1:
for j in range(C):
if distance[i][j] > 0:
answer.append(distance[i][j])
else:
if distance[i][0] > 0:
answer.append(distance[i][0])
if distance[i][C-1] > 0:
answer.append(distance[i][C-1])
if not answer:
print("IMPOSSIBLE")
else:
print(min(answer)+1)TRY 2
import sys
input = sys.stdin.readline
from collections import deque
R,C = map(int,input().split())
maze = [] # 그래프
dx = [1,-1,0,0]
dy = [0,0,1,-1]
fire = [] # 불 위치
edge = [] # 가장자리
for i in range(R):
maze.append(list(input().rstrip()))
# 지훈,불 위치 찾기
for i in range(R):
for j in range(C):
if maze[i][j] == 'J':
j_x,j_y = (i,j)
if maze[i][j] == 'F':
fire.append((i,j))
# 최단 거리 찾기
def bfs(a,b):
q = deque([])
q.append([(a,b),'J'])
for i in range(len(fire)):
q.append([(fire[i][0],fire[i][1]),'F'])
visited = [[False]*C for _ in range(R)]
count = [[0]*C for _ in range(R)]
while q:
temp = q.popleft()
x,y = temp[0]
who = temp[1]
# 지훈이 탈출 조건
if (x == 0 or x == R-1 or y == 0 or y == C-1) and who == 'J':
return count[x][y] + 1
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<R and 0<=ny<C and visited[nx][ny] == False and maze[nx][ny] != '#':
if who == 'J' and maze[nx][ny] == '.':
q.append([(nx,ny),'J'])
visited[nx][ny] = True
count[nx][ny] = count[x][y] + 1
if who == 'F' and maze[nx][ny] != 'F':
q.append([(nx,ny),'F'])
maze[nx][ny] == 'F'
return None
count = bfs(j_x,j_y)
if count == None:
print("IMPOSSIBLE")
else:
print(count)TRY 3
import sys
input = sys.stdin.readline
from collections import deque
R,C = map(int,input().split())
maze = [] # 그래프
dx = [1,-1,0,0]
dy = [0,0,1,-1]
q = deque([])
for i in range(R):
maze.append(list(input().rstrip()))
# 지훈 위치 찾기
if 'J' in maze[i]:
q.append((i,maze[i].index('J'),0))
# 불 위치 찾기
for i in range(R):
for j in range(C):
if maze[i][j] == 'F':
q.append((i,j,-1))
answer = "IMPOSSIBLE"
while q:
x,y,time = q.popleft()
# 지훈이 탈출 조건
if (x == 0 or x == R-1 or y == 0 or y == C-1) and maze[x][y] != 'F' and time > -1:
answer = time + 1
break
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<R and 0<=ny<C and maze[nx][ny] != '#':
# 지훈이
if time > -1 and maze[nx][ny] == '.':
q.append((nx,ny,time+1))
maze[nx][ny] = 'V'
# 불
elif time == -1 and maze[nx][ny] != 'F':
q.append((nx,ny,-1))
maze[nx][ny] = 'F'
print(answer)