[백준] 4179번 - 불! (파이썬)

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

# 불!
from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

N, M = map(int, input().split())
arr = []
now = deque()
fire = deque()
for i in range(N):
    arr.append(list(input().strip()))
    for j in range(M):
        if arr[i][j] == 'J':
            now.append((i, j))
            arr[i][j] = 1
        if arr[i][j] == 'F':
            fire.append((i, j))


def move():
    leng = len(now)
    for _ in range(leng):
        x, y = now.pop()
        if arr[x][y] != 'F':
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < N and 0 <= ny < M:
                    if arr[nx][ny] != '#' and arr[nx][ny] != 'F' and not visited[nx][ny]:
                        arr[nx][ny] = arr[x][y] + 1
                        visited[nx][ny] = True
                        now.appendleft((nx, ny))
                else:
                    return arr[x][y]


def fire_move():
    leng = len(fire)
    for _ in range(leng):
        x, y = fire.pop()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] != '#' and arr[nx][ny] != 'F':
                    arr[nx][ny] = 'F'
                    fire.appendleft((nx, ny))


answer = 0
visited = [[False] * M for _ in range(N)]
visited[now[0][0]][now[0][1]] = True
while True:
    answer = move()
    if answer or not now:
        break
    fire_move()

if not answer:
    print('IMPOSSIBLE')
else:
    print(answer)

 

BFS

1. 입력을 받으면서 now에 현재 위치를 입력받고 J의 자리를 숫자 1로 대체, 불의 위치도 fire에 따로 저장

2. answer가 존재하거나 now가 없어질 때 까지

    - move() : 현재 now들을 pop해서 상하좌우에 +1한 값으로 arr 업데이트, now에 appendleft

    - fire_move() : 현재 fire들을 pop해서 상하좌우에 'F'로 arr 업데이트, fire에 appendleft

3. answer가 존재하지 않으면 'IMPOSSIBLE', 존재하면 answer 프린트

 

지훈이가 움직이고 나서 불이 옮겨 붙는다.

따라서 지훈이가 이전에 있던 자리가 'F'가 될 수도 있기 때문에

현재 위치가 'F'가 아니면 상하좌우를 탐색해줘야 한다.

또한, 현재 now와 fire의 길이만큼 pop해주기 때문에

도중에 추가되는 now와 fire의 위치는 appendleft를 이용해 주어야 한다.