[Baekjoon / Python] 5427번 : 불

loveydev·2023년 4월 30일

Baekjoon

목록 보기

5/8

개요

🖱️ 문제 링크 : https://www.acmicpc.net/problem/5427

시간 제한 : 1초

메모리 제한 : 256MB

기출 : ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번

문제

⌨️ 입력

T (T <= 100) 개의 테스트 케이스를 받고,

각 케이스 마다 w * h 크기의 배열을 입력받아 상근이가 빌딩을 탈출할 수 있는지 구하는 문제

w * h크기의 배열은 최대 1000 X 1000 이다.

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.

🖨️ 출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다.

빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

해결 방법

💡 문제 이해

이제는 이런 문제 보면 너무 양산형이라는 생각이 든다.

진부한 '상하좌우 이동' 에 '최단 거리' 문제는 보자마자 BFS를 떠오르게 만들었다.

한가지 매력적인 부분은 상근이는 다음에 불이 붙을 예정인 지점은 이동 불가 였다.

( = 불이 먼저 번지고, 상근이가 이동하는 로직으로 접근)

불 번짐 -> 상근 이동 -> 불 번짐 .. 을 구현하기 위해서는

매 사이클 마다 큐에 들어 있는 길이 만큼만 반복문을 돌게 하면 된다!

Python Code

# 백준 5427 불
# 불이 날 예정인 지점은 상근이는 이동 못함
# 따라서 불을 먼저 이동시키고, 상근이가 이동하는게 논리적으로 맞음

import sys
from collections import deque
read = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# 테스트 케이스 수
T = int(read())

def burn():
    len_fire = len(fire)
    for _ in range(len_fire):
        x, y = fire.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 빌딩 범위 내에서만 불이 번짐
            if 0 <= nx < h and 0 <= ny < w :
                # 이동한 위치가 빈 공간인 경우
                if building[nx][ny] == '.':
                    building[nx][ny] = '*'
                    fire.append([nx, ny])


def escape_building():
    while queue:
        len_q = len(queue)
    
        # 현재 큐에 들어있는 길이 만큼만 움직임
        for _ in range(len_q):
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                # 빌딩 범위 내인 경우
                if 0 <= nx < h and 0 <= ny < w:
                    # 이동한 위치가 빈 공간이면서 미 방문 지역일 경우
                    if building[nx][ny] == '.' and visited[nx][ny] == 0:
                        queue.append([nx,ny])
                        visited[nx][ny] = visited[x][y] + 1

                # 빌딩 범위를 벗어난 경우 = 탈출
                elif nx < 0 or ny < 0 or nx == h or ny == w:
                    print(visited[x][y] + 1)
                    return
                
        burn()
    print('IMPOSSIBLE')
    return


for _ in range(T):
    # 빌딩 지도의 가로, 세로
    w,h = map(int,read().split())

    # '.': 빈 공간
    # '#': 벽
    # '@': 상근이의 시작 위치
    # '*': 불
    building = [ list(read().rstrip()) for _ in range(h) ]
    visited = [ [0] * w for _ in range(h) ]

    # 상근이의 위치, 불의 위치
    queue, fire = deque(), deque()

    # 상근이의 위치와 불길의 위치 업데이트
    for i in range(h):
        for j in range(w):
            if building[i][j] == '@':
                # 빈 칸으로 간주해도 됨. 초기 위치를 따로 저장해두었기에
                building[i][j] = '.'
                queue.append([i,j])

            elif building[i][j] == '*':
                fire.append([i,j])

    burn()
    escape_building()