Python) - BOJ(5427번) : 불

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

5427번: 불

---

• 해설 : 

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

 

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

 

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

예전에 풀었던 고슴도치가 탈출하는 문제인 탈출(https://recordofwonseok.tistory.com/169?category=1000045) 문제와 동일한 문제이다. bfs를 진행하는데 불이 퍼지는 행위 1번, 탈출경로를 찾는 행위 1번의 총 2회 진행하면 된다.

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
def bfs():
 
    c = [[-1]*w for _ in range(h)]
    m = 0
    c[s_queue[0][0][0]][s_queue[0][0][1]] = 0
    while f_queue[-1] or s_queue[-1]:
        f_queue.append([])
        s_queue.append([])
        for z in f_queue[m]:
            x,y = z
            for i in range(4):
                ax = x + dx[i]
                ay = y + dy[i]
                if 0 <= ax < h and 0 <= ay < w:
                    if building[ax][ay] == ".":
                        building[ax][ay] = "*"
                        f_queue[-1].append([ax,ay])
        for z in s_queue[m]:
            x,y = z
            for i in range(4):
                ax = x + dx[i]
                ay = y + dy[i]
                if 0 <= ax < h and 0 <= ay < w:
                    if building[ax][ay] == "." and c[ax][ay] == -1:
                        c[ax][ay] = c[x][y] + 1
                        building[ax][ay] = "@"
                        s_queue[-1].append([ax,ay])
                else:
                    return c[x][y]+1
 
        m+=1
    return -1
 
if __name__ == "__main__":
    testCase = int(sys.stdin.readline())
    for _ in range(testCase):
        w,h = map(int,input().split())
        building = []
        s_queue = [[]]
        f_queue = [[]]
        for _ in range(h):
            building.append(list(input()))
        for i in range(h):
            for j in range(w):
                if building[i][j] == "@":
                    s_queue[0].append([i,j])
                if building[i][j] == "*":
                    f_queue[0].append([i,j])
        answer = bfs()
 
        if answer == -1:
            print("IMPOSSIBLE")
        else:
            print(answer)