백준 5427 불 Python 3

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

5427번: 불

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ5427.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque

def spread_fire():
    size = len(fires)
    while size:
        x, y = fires.popleft()
        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            if 0 <= nx < w and 0 <= ny < h and building[ny][nx] == '.':
                fires.append([nx, ny])
                building[ny][nx] = '*'
        size -= 1

def BFS():
    while q:
        spread_fire()
        edge = len(q)
        while edge:
            x, y, sec = q.popleft()
            for ddx, ddy in zip(dx, dy):
                nx = x + ddx
                ny = y + ddy
                if 0 <= nx < w and 0 <= ny < h:
                    if building[ny][nx] == '.' and not visit[ny][nx]:
                        q.append([nx, ny, sec+1])
                        visit[ny][nx] = 1
                else: return sec + 1
            edge -= 1
    return 0


input = sys.stdin.readline
T = int(input())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
building = []
fires = deque(list())
q = deque(list())
for _ in range(T):
    w, h = map(int, input().split())
    building.clear()
    fires.clear()
    q.clear()
    visit = [[0]*w for _ in range(h)]
    for hh in range(h):
        building.append(list(input()))
        for ww in range(w):
            if building[hh][ww] == '@':
                q.append([ww, hh, 0])
                visit[hh][ww] = 1
                building[hh][ww] = '.'
            if building[hh][ww] == '*':
                fires.append([ww, hh])
    result = BFS()
    if result > 0: print(result)
    else: print("IMPOSSIBLE")

---

풀이 과정

풀이 시간 39분

간만에 좀 복잡한 BFS 문제를 풀어보았다.

상근이가 1초에 동서남북 방향으로 인접한 빈 공간으로 한 칸 이동하게 되는데, 이 때, 불이 곧 옮겨질 칸이나 불이 있는 칸으로는 이동 할 수 없다.

이렇게 이동을 하면서 건물 밖으로 벗어나는 가장 빠른 탈출 시간을 구하는 문제이다.

이때, 불도 매 1초마다 동서남북 방향으로 인접한 빈 공간에 번지게 된다.

즉, 상근이가 매 초마다 이동하기 직전에 불을 먼저 번지게 하고 그 당근이를 이동시키면 된다.

BFS로 문제를 해결할 것이기 때문에 매 초마다 1. 불번지기, 2. 상근이 이동하기를 수행해야 한다.

동일한 초에 상근이가 있을 수 있는 칸이 여러 군데 있을 수가 있다.

그리고 해당 초에 번진 불에 의해서 상근이가 이동할 수 있는 위치가 달라진다.

따라서 해당 초에 상근이의 상태들을 담은 큐 사이즈 만큼 큐에서 빼내 이동을 시켜야 매초마다 정확하게 로직을 구현할 수 있다.

import sys
from collections import deque

def spread_fire():
	#해당 초에 번져야 하는 불의 개수만큼 while문을 진행시킨다
    size = len(fires)
    while size:
        x, y = fires.popleft()
        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            #빌딩 안에 있으면서 빈 공간인 경우, 불이 번진다
            if 0 <= nx < w and 0 <= ny < h and building[ny][nx] == '.':
                fires.append([nx, ny])
                building[ny][nx] = '*'
        size -= 1

def BFS():
    while q:
    	#1초 수행
        #1. 불 번지기
        spread_fire()
        
        #2. 상근이의 위치 옮기기 - 해당 초에 상근이의 가능한 위치들은 len(q)만큼 있다
        edge = len(q)
        while edge:
            x, y, sec = q.popleft()
            
            for ddx, ddy in zip(dx, dy):
                nx = x + ddx
                ny = y + ddy
                
                #빌딩 안인 경우,
                if 0 <= nx < w and 0 <= ny < h:
                	#빈 공간인 경우, 해당 위치로 옮긴다
                    if building[ny][nx] == '.' and not visit[ny][nx]:
                        q.append([nx, ny, sec+1])
                        visit[ny][nx] = 1
                
                #빌딩 밖인 경우, 탈출 성공 함수를 빠져나간다
                else: return sec + 1
            edge -= 1
    
    #가능한 모든 위치들로 도망갔는데도 건물 안인 경우, 탈출 실패
    return 0


input = sys.stdin.readline
T = int(input())

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

#다음에 번질 불의 위치들을 담는 큐
fires = deque(list())

#[상근이의 위치, 탈출한 시간]을 담는 큐
q = deque(list())

for _ in range(T):
    w, h = map(int, input().split())
    #초기화
    building.clear()
    fires.clear()
    q.clear()
    visit = [[0]*w for _ in range(h)]
    for hh in range(h):
        building.append(list(input()))
        for ww in range(w):
        	#상근이의 시작 위치를 q에 담고, .으로 바꿔준다
            if building[hh][ww] == '@':
                q.append([ww, hh, 0])
                visit[hh][ww] = 1
                building[hh][ww] = '.'
                
            #초기에 불이 있는 위치들을 fires에 담는다    
            if building[hh][ww] == '*':
                fires.append([ww, hh])
    
    result = BFS()
    if result > 0: print(result)
    else: print("IMPOSSIBLE")
 
#시간복잡도 = O(V+E), 공간복잡도 = O(n)