[파이썬] [BFS] 백준 4179 불!

문제

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

4179번: 불!

코드

import sys
from collections import deque
input=sys.stdin.readline
queue=deque()

dx=[-1,1,0,0]
dy=[0,0,-1,1]

r,c=map(int, input().split())
graph=[list(input().rstrip()) for _ in range(r)]
visited=[[0]*c for _ in range(r)]
#아래 케이스 때문에 불을 먼저 넣어야함
for i in range(r):
    for j in range(c):
        if graph[i][j]=='F':
            queue.append([i,j,'F'])
for i in range(r):
    for j in range(c):
        if graph[i][j]=='J':
            if i==0 or i==r-1 or j==0 or j==c-1:
                print(1)
                exit(0)
            queue.append([i,j,'J'])
            visited[i][j]=1

def bfs():
    while queue:
        x,y,z = queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if z=='J':
                if nx==0 or nx==r-1 or ny==0 or ny==c-1:
                    if graph[nx][ny]!="#" and graph[nx][ny]!="F":
                        return visited[x][y]+1
                if graph[nx][ny]!="#" and graph[nx][ny]!="F" and visited[nx][ny]==0:
                    visited[nx][ny]=visited[x][y]+1
                    queue.append([nx,ny,'J'])
            elif z=='F':
                if 0<=nx<r and 0<=ny<c and graph[nx][ny]!="#" and graph[nx][ny]!='F':
                    graph[nx][ny]='F'
                    queue.append([nx,ny,'F'])
    return "IMPOSSIBLE"
print(bfs())

어려웠던 점

불이 번지는 개념을 잘못 이해해

#IMPOSSIBLE
4 4
####
#.J#
#F.#
#..#

이 케이스를 찾는데 시간이 오래 걸렸다.