[BOJ][🟡4][백준#05427] 불

문제 출처

BAEKJOON Online Judge #5427

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000) 다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

’.’: 빈 공간 ‘#’: 벽 ‘@’: 상근이의 시작 위치 ‘*’: 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 “IMPOSSIBLE”을 출력한다.

예제

입력

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

출력

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

My Sol

from collections import deque

def findsang():
    global mat
    for i in range(I):
        for j in range(J):
            if mat[i][j]=='@':
                return i, j
            
def main():
    # 불 좌표 확인
    fires = deque()
    fl = 0
    for i in range(I):
        for j in range(J):
            if mat[i][j] == '*':
                fires.append((i, j))
                fl += 1

    # 상근 좌표 확인
    ni, nj = findsang()
    sangmoves = deque()
    sangmoves.append((ni, nj))
    ml = 1

    # visit
    firevisit = [[0]*J for _ in range(I)]
    for fi, fj in fires:
        firevisit[fi][fj] = 1
    sangvisit = [[0]*J for _ in range(I)]
    sangvisit[ni][nj] = 1

    time = 1
    while sangmoves:
        # 불 이동
        for _ in range(fl):
            fi, fj = fires.popleft()
            fl -= 1

            for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                sfi, sfj = fi+di, fj+dj
                if not (0<=sfi<I and 0<=sfj<J): continue
                if firevisit[sfi][sfj]: continue
                if mat[sfi][sfj] == '#': continue
                firevisit[sfi][sfj] = 1
                fires.append((sfi, sfj))
                fl += 1

        # 상근 이동
        for _ in range(ml):
            ni, nj = sangmoves.popleft()
            ml -= 1

            for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                si, sj = ni+di, nj+dj
                if not (0<=si<I and 0<=sj<J): return time
                if firevisit[si][sj]: continue
                if sangvisit[si][sj]: continue
                if mat[si][sj]=='#': continue
                sangvisit[si][sj] = 1
                sangmoves.append((si, sj))
                ml += 1
        time += 1

    return 'IMPOSSIBLE'

T = int(input())
for _ in range(T):
    J, I = map(int, input().split())
    mat = [list(input()) for _ in range(I)]
    print(main())

BFS를 2중으로 사용하는 문제였다. 불이 이동하고, 상근이가 이동하는 상황을 고려해서 상근이가 범위 외로 이동하게 된다면 탈출하기까지 while문의 반복 횟수를 반환하고, 상근이가 이동할 수 있는 좌표의 집합큐인 sangmoves가 빈다면, 불이나 여러 요인으로 상근이가 이동할 수 없는 것이므로 IMPOSSIBLE을 반환한다.

이 반환값을 테스트케이스마다 출력해주면 되겠다.

결과

맞았습니다!!