[백준`G4] 4179 - 불! (Python)

문제 설명

https://www.acmicpc.net/problem/4179

4179번: 불!

---

문제 풀이

bfs를 두 번을 해야 하는 문제는 처음이라 풀이 방향을 잡는데 어려웠다

일단 불이 확산되는 시간을 구하고, 그 다음에 지훈이가 탈출할 수 있는지 확인해야 하기 때문에

BFS를 두 번 수행해야 한다

 

지훈이가 미로 공간을 벗어나면 미로를 탈출하는 것이기 때문에 바로 return을 해줬다

BFS는 거리 순서대로 탐색해서 무조건 최소 시간이 맨 처음에 들어오기 때문에 바로 리턴을 해주는 게 포인트! 

지훈이가 지나갈 수 없으면 continue를 해주고,

불이 지훈이가 가는 시간보다 늦게 확산되거나 불이 지나가지 않는 공간일 때 큐에 넣고 거리를 계산해주었다

 

from collections import deque


def fire_bfs():
    while fq:
        x, y = fq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c or maze[nx][ny] == '#':
                continue
            if maze[nx][ny] == '.' and fire[nx][ny] == 0:
                fq.append((nx, ny))
                fire[nx][ny] = fire[x][y] + 1
    return


def j_bfs():
    ret = 'IMPOSSIBLE'
    while jq:
        x, y = jq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                return escape[x][y]
            if maze[nx][ny] == '#' or escape[nx][ny] > 0:
                continue
            # 불이 지훈이가 가는 시간보다 늦게 확산되거나, 불이 지나가지 않는 공간일 때
            if fire[nx][ny] > escape[x][y] + 1 or fire[nx][ny] == 0:
                jq.append((nx, ny))
                escape[nx][ny] = escape[x][y] + 1
    return ret


r, c = map(int, input().split())
maze = [list(input()) for _ in range(r)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

jq = deque()
fq = deque()
fire = [[0 for b in range(c)] for a in range(r)]
escape = [[0 for _b in range(c)] for _a in range(r)]

for x, mz in enumerate(maze):
    for y, m in enumerate(mz):
        if m == "J":
            jq.append((x, y))
            escape[x][y] = 1
        elif m == "F":
            fq.append((x, y))
            fire[x][y] = 1

fire_bfs()
result = j_bfs()

print(result)