[백준] 4179. 불! (Python)

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

4179번: 불!

 

from collections import deque

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

def setfire():
    global fires
    temp = []
    for y, x in fires:
        for i, j in dir:
            dy, dx = y+i, x+j
            if 0 <= dy < Y and 0 <= dx < X and miro[dy][dx] == '.':
                miro[dy][dx] = 'F' # 불 지르기
                temp.append((dy, dx))
    fires = temp

def BFS(y, x):
    q = deque()
    q.append((y, x, 0)) # y, x, cnt
    check[y][x] = 1
    fcnt = 0
    while q:
        ny, nx, cnt = q.popleft()
        if cnt > fcnt: # 지훈이가 이동한 다음 불 확산
            setfire()
            fcnt += 1
        if miro[ny][nx] == 'F':continue # 불 확산으로 현재 자리가 불이 났을 수도... -> 불 나면 패스
        for i, j in dir:
            dy, dx = ny+i, nx+j
            if 0 <= dy < Y and 0 <= dx < X :
                if check[dy][dx] == 0 and miro[dy][dx] == '.': # 범위 내이고 이동 가능하면 이동
                    check[dy][dx] = 1
                    q.append((dy, dx, cnt+1))
            else: # 범위 밖 => 탈출 가능
                return cnt+1
    return "IMPOSSIBLE"


Y, X = map(int, input().split())
jihoon = []
fires = []
miro = []
check = [[0]*X for _ in range(Y)]

for y in range(Y):
    temp = list(input())
    for x in range(X):
        if temp[x] == 'J': # 지훈이를 발견하면
            jihoon = (y, x) # 좌표 저장
            temp[x] = '.'
        elif temp[x] == 'F': # 불난 곳을 발견하면
            fires.append((y, x)) # 좌표 저장
    miro.append(temp)

print(BFS(jihoon[0], jihoon[1]))