📄 문제
백준
난이도 : Gold 4
문제 제목 : 불!
✏️ 풀이 1
import sys
from collections import deque
input = sys.stdin.readline
r, c = map(int, input().split())
matrix = [list(input().strip()) for _ in range(r)]
fire_dist = [[r * c] * c for _ in range(r)]
jihun_dist = [[r * c] * c for _ in range(r)]
time = 0
dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)
def bfs(start_points, who):
if who == "fire":
deq = deque(start_points)
for point_y, point_x in start_points:
fire_dist[point_y][point_x] = 0
else:
deq = deque(start_points)
for point_y, point_x in start_points:
jihun_dist[point_y][point_x] = 0
while deq:
y, x = deq.popleft()
current_dist = fire_dist[y][x] if who == "fire" else jihun_dist[y][x]
if who != "fire" and (y == 0 or x == 0 or y == r - 1 or x == c - 1):
print(current_dist + 1)
sys.exit(0)
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if ny < 0 or nx < 0 or ny >= r or nx >= c:
continue
if who == "fire":
if fire_dist[ny][nx] != r * c or matrix[ny][nx] != ".":
continue
fire_dist[ny][nx] = current_dist + 1
else:
if jihun_dist[ny][nx] != r * c or matrix[ny][nx] != "." or fire_dist[ny][nx] <= current_dist + 1:
continue
jihun_dist[ny][nx] = current_dist + 1
deq.append([ny, nx])
jihun_points = []
fire_points = []
flag = False
for i in range(r):
for j in range(c):
if matrix[i][j] == "J":
jihun_points.append([i, j])
elif matrix[i][j] == "F":
fire_points.append([i, j])
bfs(fire_points, "fire")
bfs(jihun_points, "jihun")
print("IMPOSSIBLE")BFS의 기본적인 응용 문제로, 시작점이 두 종류일 때의 문제이다.
결론적으로 불에 대한 BFS, 지훈이에 대한 BFS 모두 돌림으로서 해결이 가능하다.
먼저 불에 대한 BFS를 돌린 후, 각 칸에 불이 도달하기까지 걸리는 시간을 저장한다.
그리고 지훈이에 대한 BFS를 돌리면서, 각 시간별로 지훈이가 해당 칸으로 이동할 수 있는지 확인한다.
예를 들어 어떤 칸에 지훈이가 오기 전에 불이 붙었거나, 또는 지훈이가 올 때에 불이 붙는다면 지훈이는 해당 칸으로 이동할 수 없다.
BFS를 알고 있으면서 위의 사항들을 유의하고 위의 코드를 본다면 이해가 쉽게 될 것이다.
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '4179. 불!'
GitHub - [9강] BFS/연습문제 '4179. 불!'
BFS의 대표적인 응용 유형인 '시작점이 두 종류일 때' 유형의 가장 기본적인 문제라 정리를 해보았다.
다른 사람들의 풀이를 몇 가지 찾아보니, bfs 함수 내에 while fire_deq문과 while jihun_deq을 순서대로 두는 경우가 많았다.
그 방법이 좀 더 깔끔할 것 같기도 하여 그렇게 다시 풀어 정리해볼까 했는데 위의 풀이를 이해한다면 굳이 또 정리를 하지는 않아도 될 것 같아 생략한다.
추후에 이 문제를 다시 풀어보게 된다면 '✏️ 풀이 2'로 추가해보겠다.
