[BOJ] 4179. 불!

📌 문제 제목

문제 링크: BOJ 4179

---

🗒️ 문제 설명

미로에 지훈이와 불이 난 위치, 벽이 존재할 때, 지훈이를 탈출시켜야 한다.

지훈이와 불은 매 분 상하좌우로 이동한다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

시간 제한: 1초

메모리 제한: 256MB

1 <= R, C <= 1,000

---

💡 문제 해결 아이디어

• 이차원 for 문을 돌며 지훈이와 불이 있는 위치를 알아야 함.
  
  • 지훈이와 불의 위치를 각 큐를 만들어 넣고 dist 배열도 각자 만들어서 0으로 초기화 시킨다.
• 불 BFS를 먼저 수행한다.
• 지훈이 BFS를 수행하며 불이 오기 전에 갈 수 있으면 이동한다.
• 그래프를 빠져나갈 수 있으면 jihun_dist[xp][yp] + 1을 출력한다.
• 아니라면 IMPOSSIBLE을 출력한다.

---

⌛️ 시간 복잡도

• O(RC)

---

✅ 최종 코드

import sys
from collections import deque
input = sys.stdin.readline

R, C = map(int, input().split())
graph = [input().strip() for _ in range(R)]

direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

fire_queue = deque([])
fire_dist = [[-1] * C for _ in range(R)]
jihun_queue = deque([])
jihun_dist = [[-1] * C for _ in range(R)]

for i in range(R):
    for j in range(C):
        if graph[i][j] == 'F':
            fire_queue.append((i, j))
            fire_dist[i][j] = 0
        elif graph[i][j] == 'J':
            jihun_queue.append((i, j))
            jihun_dist[i][j] = 0

while fire_queue:
    xp, yp = fire_queue.popleft()
    for dx, dy in direction:
        nx, ny = xp + dx, yp + dy
        if not (0 <= nx < R and 0 <= ny < C):
            continue
        if graph[nx][ny] != '#' and fire_dist[nx][ny] == -1:
            fire_queue.append((nx, ny))
            fire_dist[nx][ny] = fire_dist[xp][yp] + 1

while jihun_queue:
    xp, yp = jihun_queue.popleft()
    for dx, dy in direction:
        nx, ny = xp + dx, yp + dy
        if not (0 <= nx < R and 0 <= ny < C):
            print(jihun_dist[xp][yp] + 1)
            exit(0)
        if not (jihun_dist[xp][yp] + 1 < fire_dist[nx][ny] or fire_dist[nx][ny] == -1):
            continue
        if graph[nx][ny] == '.' and jihun_dist[nx][ny] == -1:
            jihun_queue.append((nx, ny))
            jihun_dist[nx][ny] = jihun_dist[xp][yp] + 1

print("IMPOSSIBLE")