[백준] 4179 - 불!

문제 링크

문제 제목

문제 요약

미로에서 지훈이와 불이 각자 매 분마다 수평 또는 수직으로 한 칸씩 이동할 수 있는 상황에서, 지훈이가 불이 붙기 전에 미로의 가장자리에 도달해 탈출할 수 있는지 판단하고, 탈출이 가능하면 최소 탈출 시간을 출력해야 합니다. 만약 불이 더 빠르게 퍼지거나 지훈이가 탈출할 수 없는 경우, "IMPOSSIBLE"을 출력해야 합니다.

푼 방법

• deque를 사용하여 불과 지훈이의 위치를 각각 관리하고 BFS 탐색으로 최단 시간을 계산합니다.
• 불과 지훈이의 이동을 BFS로 처리해 매 분마다 확산과 이동을 동시에 수행하여 최단 시간을 계산합니다.
• 훈이가 미로의 가장자리에 도달하면 탈출 시간을 출력, 불이 모든 공간을 확산하거나 이동 가능한 경로가 없으면 IMPOSSIBLE을 출력합니다.

 

정답 코드

import sys
from collections import deque

r, c = map(int, sys.stdin.readline().split())
world = []
for _ in range(r):
    world.append(list(sys.stdin.readline().rstrip()))
    
move_y = [-1, 0, 1, 0]
move_x = [0, 1, 0, -1]

fireq = deque()
jq = deque()

for i in range(r):
    for j in range(c):
        if world[i][j] == 'J':
            jq.append((i, j))
        elif world[i][j] == 'F':
            fireq.append((i,j))

dist = [[-1 for _ in range(c)] for _ in range(r)]
dist[jq[0][0]][jq[0][1]] = 0

def fire_bfs():
    fire_len = len(fireq)
    
    for _ in range(fire_len):
        y, x = fireq.popleft()
        for i in range(4):
            ny, nx = y+move_y[i], x+move_x[i]
            
            if 0<=ny<r and 0<=nx<c:
                if world[ny][nx] =='.':
                    world[ny][nx] = 'F'
                    fireq.append((ny, nx))
        
    return False
                
def J_bfs():
    j_len = len(jq)
    
    for _ in range(j_len):
        y, x = jq.popleft()
        for i in range(4):
            ny, nx = y+move_y[i], x+move_x[i]
            if ny == -1 or ny == r or nx == -1 or nx == c:
                print(dist[y][x] + 1)
                return True
            if world[ny][nx] == '.' and dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                jq.append((ny, nx))
    return False

while jq:
    fire_bfs()
    if J_bfs():
        break
else:
    print("IMPOSSIBLE")