[ 5427 ] [ BFS ] 불

문제 설명

---

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

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

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

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

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

출력

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

---

풀이 과정

1. 전체적으로 두가지 과정으로 진행된다.
   • 불이 퍼지는 과정
   • 상근이가 이동하는 과정
2. 상근이가 이동하는 경우(1초가 지난 경우), 이동하기 전에 불을 확산시킨다.
   • 이 부분은, bfs에서 queue에 step을 따로 저장하여, 이전 step과 현재 step이 다른 경우 이동한 것으로 간주
   • 따라서, 이전 step과 현재 step이 다른 경우 불을 한번 확산시키면 된다.
3. 불을 확산하는 경우는 한번 이루어지면 되므로, 함수로 구현.
   • 불의 위치를 입력받으면, 불의 위치에서 상하좌우로 불을 확산시키도록 구현
4. 배열의 인덱스를 벗어나는 경우, 탈출한 것이므로 step 출력
5. step을 출력하지 못하고 queue가 비게 되면, 탈출이 실패한 것이므로 IMPOSSIBLE 출력

• queue에서 다음 위치를 뺏을 때, 해당 위치에 불이 번져있다면 못가는 것임.. 이부분 처리를 안해줘서 1시간정도 걸린듯.

---

소스 코드

import sys
from collections import deque
import copy

input = sys.stdin.readline

T = int(input().rstrip())

def expand(matrix, fire):
    temp = []
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    w, h = len(matrix[0]), len(matrix)
    for x, y in fire:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                if matrix[nx][ny] == '.':
                    matrix[nx][ny] = '*'
                    temp.append([nx, ny])

    return temp

for _ in range(T):
    # 입력부
    w, h = map(int, input().rstrip().split())
    matrix = [list(input().rstrip()) for _ in range(h)]
    # 초기
    visited = [[False] * w for _ in range(h)] 
    person_x, person_y = 0, 0
    fire = []
    # 불, 사람의 위치 저장
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == '@':
                person_x, person_y = i, j
            if matrix[i][j] == '*':
                fire.append([i, j])

    queue = deque([[person_x, person_y, 0]])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[person_x][person_y] = True
    before = 0
    end = False
    while queue:
        x, y, step = queue.popleft()
        # 이동 => 불 확산
        if before != step:
            # 불 확산 + 확산된 불의 위치 저장
            fire = expand(matrix, fire)
            before = step

        if matrix[x][y] == '*':
            # 이번에 갈 곳에 불이 이미 번졌으면 못감
            continue

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                if not visited[nx][ny] and matrix[nx][ny] == '.':
                    visited[nx][ny] = True
                    queue.append([nx, ny, step+1])
            else:
                # 범위 벗어나면 탈출한것이므로 출력
                print(step+1)
                end = True
                break
        if end:
            break
    if not end:
        print("IMPOSSIBLE")