[백준] [Python] 4179번 불! - BFS

www.acmicpc.net/problem/4179

4179번: 불!

 

Python

from collections import deque
#import time
import sys

#s = time.time()
r, c = map(int, sys.stdin.readline().split())    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

visitJ = []
visitF = []

qJ = deque()
qF = deque()

maze = []
for a in range(r):
    maze.append(list(sys.stdin.readline().rstrip()))
    visitJ.append([0]*c)
    visitF.append([0]*c)
    for b in range(c):
        if maze[a][b] == 'F': qF.append((a,b));
        elif maze[a][b] == 'J': qJ.append((a,b));

#불이 번지는 시간을 visitF에 저장
while (len(qF) != 0):
    pos = qF[0]
    qF.popleft()
    for i in range(4):
        nx = pos[0] + dx[i]
        ny = pos[1] + dy[i]
        if (0<=nx<r and 0<=ny<c):
            if (visitF[nx][ny] == 0 and maze[nx][ny] != '#'):
                visitF[nx][ny] =  visitF[pos[0]][pos[1]]+1
                qF.append((nx,ny))


#불이 번지는 시간에 따른
#지훈이의 대피 시간 계산
while (len(qJ) != 0):
    pos = qJ[0]
    qJ.popleft()
    for i in range(4):
        nx = pos[0] + dx[i]
        ny = pos[1] + dy[i]
        
        if not (0<=nx<r and 0<=ny<c): #범위 밖 == 탈출 성공
            print(visitJ[pos[0]][pos[1]]+1)
            #큐에는 거리 순으로 들어가므로 첫 탈출 시간을 출력하자
            sys.exit(0)
            
        if (visitJ[nx][ny] == 0 and maze[nx][ny] != '#'):
            #벽이 아니며, 한번도 가보지 않은 곳일 때
            if ( visitF[nx][ny]==0 or visitJ[pos[0]][pos[1]]+1 < visitF[nx][ny]):
                #불이 난 적이 없거나, 불이 오기 전에 갈 수 있는 곳이라면
                visitJ[nx][ny] =  visitJ[pos[0]][pos[1]]+1
                qJ.append((nx,ny))

print('IMPOSSIBLE')                   
#print(time.time()-s)

 

 

 

 

BFS 기초 문제와 다른 점

• 진행경로가 시간의 경과에 따라 달라진다
  • 시작점이 두 개이며 동시에 시작할 경우, 두 시작점에 대해서 각각 BFS를 실행한다.
  • 대신 한쪽에 영향을 받는 쪽을 이후에 실행한다.
  • 자신이 먼저 왔는지에 대한 여부뿐만 아니라 한 번도 불이 온 적 없는지 검사하는 것을 잊지말자