[백준][5427] 불

• Problem Link : https://www.acmicpc.net/problem/5427

문제

상근이가 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물에 불이 났을때 상근이가 무사히 탈출할 수 있는지, 얼마나 빨리 탈출할 수 있는지 구하여라.
불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로는 이동할 수 없다.

입력

• 첫째 줄, 테스트 케이스의 개수가 주어진다.
• 각 테스트 케이스의 첫째 줄에는 너비와 높이 w, h가 주어진다.
• h개 줄에 w개의 문자로 빌딩의 지도가 주어진다.
  • '.' : 빈 공간
  • '#' : 벽
  • '@' : 상근이의 시작 위치
  • '*' : 불

출력

탈출하는데 가장 빠른 시간을 출력, 탈출할 수 없다면 "IMPOSSIBLE"을 출력한다.

풀이

기본적인 BFS 문제와 형태가 동일하나 이 문제는 이동하는 개체가 불과 상근이 두 가지라는 점이다. 상근이는 불이 옮겨진 칸이나 불이 붙으려는 칸으로는 이동할 수 없기때문에 항상 불이 번진 후에 상근이의 이동 BFS 연산을 수행하여야 한다.

기존 BFS 코드의 경우에는 while q : 연산으로 계속해서 q에 원소가 남아있으면 BFS 연산을 실행했다. 하지만 이 문제는 초 마다 불의 확산과 상근이의 이동을 수행해야하기 때문에 1초에 불이 옮겨진 후의 상근이의 움직임, 2초에 불이 옮겨진 후의 상근이의 움직임을 순차적으로 구해야한다.

위의 경우를 for문으로 해결했다. 기존에 불이 붙어있는 위치는 fire_q에 저장되어있다. 그렇다면 그 다음 시간에 불이 붙은 장소는 어디일까? 바로 직전의 fire_q의 원소들을 빼낸 후 BFS 연산으로 다시 fire_q에 들어온 장소에 불이 붙는다고 할 수 있다. 그렇기에 while fire_q가 아니라 for문을 써서 전의 시간에 큐에 들어있는 불의 개수만큼만 빼내서 다음 시간대에 불이 옮겨지는 장소를 넣는것이다. (만약 while을 사용한다면 fire_q에 원소가 있다고 판단해서 상근이가 움직이기도 전에 모든 건물을 태워버릴 것이다.)

상근이의 움직임도 동일하다. 상근이의 경우도 자신이 움직인 후에 다시 불을 옮기는 연산을 수행하러 가야하기 때문에 초 단위로 끊어서 BFS 연산을 수행해야했고 이를 for 문으로 수행했다.

for i in range(len(q)) : 라는 코드를 쓰면 해당 반복문이 실행될 때의 q 원소 갯수를 기준으로 for문이 반복된다. 중간에 q에 원소가 삽입되더라도 반복문이 계속 수행되거나 하지는 않는다.

코드

import sys
from collections import deque

input = sys.stdin.readline

di = [1,0,-1,0]
dj = [0,1,0,-1]

def fire_bfs() :
    for i in range(len(fire_q)) :
        i, j = fire_q.popleft()
        
        for d in range(4) :
            ni = i + di[d]
            nj = j + dj[d]
            if 0<=ni<h and 0 <= nj < w and graph[ni][nj] == '.'  :
                fire_q.append([ni, nj])
                graph[ni][nj] = '*'
    
def bfs() :
    while q :
        fire_bfs()
        for _ in range(len(q)) :
            i, j, depth = q.popleft()
            if i == 0 or i == h-1 or j == 0 or j == w-1 :
                print(depth+1)
                return
            
            for d in range(4) :
                ni = i + di[d]
                nj = j + dj[d]
                if 0<=ni<h and 0 <= nj < w and graph[ni][nj] == '.' :
                    q.append([ni,nj,depth+1])
                    graph[ni][nj] = '-'
            
            #for g in graph :
            #    print("".join(g))
            #print()
        
    print('IMPOSSIBLE')
        
t = int(input().rstrip())
for _ in range(t) : 
    w, h = map(int, input().rstrip().split())
    graph = [list(input().rstrip()) for _ in range(h)]

    q = deque()
    fire_q = deque()

    for i in range(h) :
        for j in range(w) :
            if graph[i][j] == '@' :
                q.append([i,j,0])
                graph[i][j] = '-'
            elif graph[i][j] == '*' :
                fire_q.append([i, j]) 
                
    bfs()