백준 4179: 불!(파이썬)

💡 문제 요약
격자판 미로에서 지훈(J)이 탈출구 없이 경계를 벗어나야 한다. 매 분 불(F)이 네 방향으로 퍼지므로, 지훈은 불이 닿기 전 안전한 경로를 찾아야 한다.

---

🧠 문제 배경

• R×C 크기, 빈칸 ./벽 #/지훈 J/불 F.
• 매 분 불과 지훈이 동시에 한 칸씩 네 방향 이동.
• 지훈이 미로 경계를 벗어나면 탈출.
• 불 또는 불이 도달 예정인 칸에는 지훈 입장 불가.

---

🔍 기존(직관) 접근

• 매 이동마다 지훈 BFS 내부에서 불 BFS를 호출 → 지훈의 각 위치마다 불 확산을 재계산.
• 시간 복잡도 O((RC)²)로 R,C 최대 1000일 때 불가능.

# (의사 코드)
def escape_time(maze):
    while 지훈 큐:
        jx, jy, t = 지훈 이동
        불 확산 = BFS_from_all_F()
        if (jx,jy) 안전(t, 불 확산): enqueue

---

🔧 개선 접근: 두 단계 BFS
1️⃣ 불 BFS: 모든 초기 불 위치에서 시작해 각 칸에 불이 도달하는 최소 시간을 fire_time 배열에 기록 (O(RC)).
2️⃣ 지훈 BFS: 지훈의 시작점에서 BFS, fire_time[nx][ny] > jihoon_time+1 조건 만족 시만 이동. 경계를 벗어나면 즉시 종료.

from collections import deque
INF = float('inf')

# 1) 불 BFS
fire_time = [[INF]*C for _ in range(R)]
q = deque()
for i in range(R):
    for j in range(C):
        if maze[i][j]=='F':
            fire_time[i][j]=0
            q.append((i,j,0))
while q:
    x,y,t = q.popleft()
    for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
        nx,ny = x+dx, y+dy
        if 0<=nx<R and 0<=ny<C and maze[nx][ny]=='.' and fire_time[nx][ny]>t+1:
            fire_time[nx][ny] = t+1
            q.append((nx,ny,t+1))

# 2) 지훈 BFS
jihoon_time = [[INF]*C for _ in range(R)]
sx, sy = start_J
jihoon_time[sx][sy]=0
q = deque([(sx,sy,0)])
ans = None
while q:
    x,y,t = q.popleft()
    # 경계 탈출
    if x==0 or y==0 or x==R-1 or y==C-1:
        ans = t+1
        break
    for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
        nx,ny,nt = x+dx, y+dy, t+1
        if 0<=nx<R and 0<=ny<C and maze[nx][ny]=='.' \
           and jihoon_time[nx][ny]>nt and fire_time[nx][ny]>nt:
            jihoon_time[nx][ny]=nt
            q.append((nx,ny,nt))

print(ans if ans else "IMPOSSIBLE")

---

✅ 성능 비교 및 결론

구분 직관 접근 두 단계 BFS

시간 복잡도	O((RC)²)	O(RC + RC) = O(RC)
연산 횟수	최대 10¹² 가능	약 2×10⁶

• 핵심: 불 확산을 한 번만 계산하고, 지훈 이동에서만 조건 검사 → O(R×C) 내 해결 가능