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

정석 풀이가 아닐수도 있습니다

풀이

요약

• 다음의 과정을 통해 풀이하였다.

  1. 문자열 지도를 정수형으로 변환 및 불 위치와 시작 위치 저장
  2. 불이 퍼지는 시간을 BFS 탐색으로 시작 위치에 기록
  3. 시작 위치에서 BFS로 탐색하며 탈출 가능 여부 및 시간 확인

설명

###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######

• 다음과 같이 문자열로 주어진 지도를 숫자로 변환하여 IF 문을 이용하기 수월하도록 하였다.
• 먼저 h * w개의 INF 값으로 초기화된 지도를 별도로 만든다.

# 헷갈릴까봐 INF 대신 기호 사용
∞∞∞∞∞∞∞
∞∞∞∞∞∞∞
∞∞∞∞∞∞∞
∞∞∞∞∞∞∞
∞∞∞∞∞∞∞
∞∞∞∞∞∞∞

• 이제 한 줄씩 문자열을 입력받으면서, for loop를 통해 각 구역이 어떤 종류인지 확인한다.
  • 빈 공간(.)이면 그대로 둠
  • 벽(#)이면 -1로 변환
  • 불(*)이면 해당 위치를 별도 배열에 저장하고 0으로 변환
  • 상근이의 시작 위치(@)면 시작 위치 변수에 저장
• 모든 입력을 받고나면 아래와 같은 상태가 된다. ``` -1 -1 -1 ∞ -1 -1 -1 -1 0 -1 ∞ -1 0 -1 -1 ∞ ∞ ∞ ∞ ∞ -1 -1 ∞ ∞ ∞ ∞ ∞ -1 -1 ∞ ∞ ∞ ∞ ∞ -1 -1 -1 -1 -1 -1 -1 -1

불 위치 저장 변수

fires < [(1, 1), (1, 5)]

시작 위치

start = (4, 3)

- 이제 불 위치를 저장한 변수를 꺼내어 BFS 탐색을 하면서 지도에 어느 시간에 불이 번지는지를 기록한다.


- for loop을 통해 `fires`에 저장된 좌표를 하나씩 꺼내어 지도를 갱신한다.
- BFS 탐색시 `time` 변수를 두어 현재 time보다 큰 값으로만 이동할 수 있도록 하면 방문체크를 하지 않아도 된다.

for x, y in fires: (1, 1) -1 -1 -1 5 -1 -1 -1 -1 0 -1 4 -1 0 -1 -1 1 2 3 4 5 -1 -1 2 3 4 5 6 -1 -1 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1

(1, 5) -1 -1 -1 5 -1 -1 -1 -1 0 -1 4 -1 0 -1 -1 1 2 3 2 1 -1 -1 2 3 4 3 2 -1 -1 3 4 5 4 3 -1 -1 -1 -1 -1 -1 -1 -1

- 이제 시작 위치부터 BFS 탐색을 시작한다.


- 상근이가 떠남과 동시에 불이 옮겨 붙는 것은 상관 없으므로, 불이 붙는 시간을 갱신할 때와 마찬가지로 `time` 변수를 두어 현재 time 보다 큰 값으로 이동할 수 있도록 한다.
    - 중복 방문을 방지하기 위해 현재 time으로 board를 갱신하였으나, 생각해보니 board를 다시 사용하지 않으므로 그냥 0으로 초기화해도 될 것 같다.
- 상근이가 이동할 위치가 이차원 리스트의 index 범위를 벗어난 곳이면 탈출했다는 뜻이므로 이동 시간을 반환하고, 모든 BFS 탐색이 끝날 때까지 탈출하지 못하면 `IMPOSSIBLE`을 반환한다.

상근이 이동 후 지도

-1 -1 -1 4 -1 -1 -1 -1 0 -1 3 -1 0 -1 -1 1 2 2 2 1 -1 -1 2 2 1 2 2 -1 -1 2 1 0 1 2 -1 -1 -1 -1 -1 -1 -1 -1

## 코드

```python
import sys
from collections import deque
input = sys.stdin.readline

INF = 2147000000

T = int(input())
DX = [-1, 0, 1, 0]
DY = [0, 1, 0, -1]


def BFS(start, board):
    que = deque()
    que.append((start[0], start[1], 1))
    while que:
        x, y, time = que.popleft()
        for n in range(4):
            xx = x + DX[n]
            yy = y + DY[n]
            # 우선 탈출 여부 체크
            if 0 <= xx < h and 0 <= yy < w:
                # 이동할 수 있는 경우
                if time < board[xx][yy]:
                    board[xx][yy] = time
                    que.append((xx, yy, time+1))
            # 인덱스를 벗어난 경우는 탈출한 것
            else:
                return time
    return 'IMPOSSIBLE'


for _ in range(T):
    w, h = map(int, input().split())
    # 실제로 사용할 지도를 초기화
    board = [[INF] * w for _ in range(h)]
    fires = []

    # 빌딩 입력받기
    for i in range(h):
        temp = input().rstrip()
        for j in range(w):
            if temp[j] == '.':
                continue
            if temp[j] == '#':
                board[i][j] = -1
            elif temp[j] == '*':
                board[i][j] = 0
                fires.append((i, j))
            else:
                board[i][j] = -1
                start = (i, j)
    # 불이 번지는 시간을 보드에 기록
    for i, j in fires:
        que = deque()
        que.append((i, j, 1))
        while que:
            x, y, time = que.popleft()
            for n in range(4):
                xx = x + DX[n]
                yy = y + DY[n]
                # 이미 다른 곳에서 옮겨붙는 불이 있으면 탐색 X
                if 0 <= xx < h and 0 <= yy < w and time < board[xx][yy]:
                    board[xx][yy] = time
                    que.append((xx, yy, time+1))
    # 사람 탐색
    print(BFS(start, board))

추가 문제

3055. 탈출도 동일한 방법으로 풀 수 있다.