문제 링크

Question

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

Input

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이 난 공간

J는 입력에서 하나만 주어진다.

Output

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

Solution

문제를 풀기 위해서 크게 두 가지 단계로 접근하였다.

  1. 미로 내 각 위치에서 불이 도달하는 데 까지 걸리는 시간 구하기
  2. 특정 시간에서 지훈이가 갈 수 있는 모든 경로에 불이 있는지 확인하기

우선적으로, 미로 내 각 위치에서 불이 도달하는 데 까지 걸리는 시간을 구하기 위해서 미로와 같은 크기의 새로운 리스트를 선언하여 BFS를 통해 불이 이동할 수 있는 모든 위치에서 불이 제일 빠르게 도달하는 시간을 구해주었다.
이때, 불의 개수는 1개 이상이 될 수 있으므로, 모든 불의 시작 지점을 초기 Queue에 넣은 후 BFS를 진행하여야 올바르게 정답을 구할 수 있다.

def get_fire_board(board: List[str], point_list: List[Tuple[int, int]], R: int, C: int):
    visited = [[False] * C for _ in range(R)]
    queue = deque([])
    fire_board = [[-1 for _ in range(C)] for _ in range(R)]

    for row, col in point_list:
        visited[row][col] = True
        queue.append(((row, col), 0))
        fire_board[row][col] = 0

    while queue:
        (cur_row, cur_col), level = queue.popleft()
        for drow, dcol in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_row = cur_row + drow
            next_col = cur_col + dcol

            if not (0 <= next_row < R and 0 <= next_col < C):
                continue
            if visited[next_row][next_col]:
                continue
            if board[next_row][next_col] == '#':
                continue

            visited[next_row][next_col] = True
            fire_board[next_row][next_col] = level + 1
            queue.append(((next_row, next_col), level + 1))
    return fire_board

여기서 board는 전체 미로 정보를 담고 있는 리스트이고, point_list는 불이 난 지점인 F의 모든 좌표를 모은 리스트이다.
시작 순간을 0으로 하여 모든 가능한 경로에 도달하는 최소 시간을 갖도록 BFS를 통해 구현하였다.
(즉, fire_board 내 특정 위치의 값이 2라면, 이는 최소 2분 뒤에는 해당 위치에 불이 도달한다는 의미이다.)

 

앞서 구한 fire_board와 전체 미로 정보 board를 가지고, 지훈이가 탈출할 수 있는지 여부와 최소 탈출 시간을 BFS를 통해서 찾아낼 수 있다. 지훈이가 탈출하는 경우와 탈출하지 못하는 경우는 다음과 같다.

  • 탈출 가능: 지훈이가 지나갈 수 있는 모든 경로 중 불의 확산보다 빠르게 미로의 가장자리에 도달하는 경로가 최소 1개 존재한다.
  • 탈출 불가능: 지훈이가 특정 시간에 지나갈 수 있는 모든 경로에 불이 이미 존재한다.

따라서, BFS를 통해 각 시간에 지날 수 있는 모든 경로를 순회하면서 fire_board의 정보를 참고하여 해당 시간에 해당 경로에 불이 존재하는지 여부를 판단한다면 위 조건을 판별할 수 있다.

def solution(board: List[str], init_point: Tuple[int, int], fire_point_list: List[Tuple[int, int]]):
    R, C = len(board), len(board[0])
    fire_board = get_fire_board(board, fire_point_list, R, C)

    visited = [[False] * C for _ in range(R)]
    visited[init_point[0]][init_point[1]] = True
    queue = deque([(init_point, 0)])

    while queue:
        (cur_row, cur_col), level = queue.popleft()

        if cur_row == 0 or cur_row == R-1 or cur_col == 0 or cur_col == C-1:
            return level

        for drow, dcol in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_row = cur_row + drow
            next_col = cur_col + dcol

            if not (0 <= next_row < R and 0 <= next_col < C):
                continue
            if visited[next_row][next_col]:
                continue
            if board[next_row][next_col] == '#':
                continue
            if 0 <= fire_board[next_row][next_col] <= (level + 1):
                continue

            visited[next_row][next_col] = True
            queue.append(((next_row, next_col), level + 1))
    return -1

여기서 init_point는 지훈이의 시작점이다.


14번째 줄에서처럼, 지훈이가 미로의 가장자리에 도달하면 그때까지 걸린 시간을 반환한다. (실제 탈출 시간은 1분 뒤이다.) 또한 0 <= fire_board[next_row][next_col] <= (level + 1) 조건을 만족한다면, 이는 이동할 경로에 이미 불이 존재하거나, 이동함과 동시에 불이 확산된다는 의미이므로 해당 경로를 선택할 수 없다. 최종적으로 BFS 탐색이 끝날 때까지 가장자리에 도달할 수 없다면, 탈출 불가능이라는 의미이므로 -1을 반환하도록 한다.

 

전체 정답 코드는 아래와 같다.

import sys
from collections import deque
from typing import List, Tuple
input = lambda: sys.stdin.readline().strip()

def get_fire_board(board: List[str], point_list: List[Tuple[int, int]], R: int, C: int):
    visited = [[False] * C for _ in range(R)]
    queue = deque([])
    fire_board = [[-1 for _ in range(C)] for _ in range(R)]

    for row, col in point_list:
        visited[row][col] = True
        queue.append(((row, col), 0))
        fire_board[row][col] = 0

    while queue:
        (cur_row, cur_col), level = queue.popleft()
        for drow, dcol in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_row = cur_row + drow
            next_col = cur_col + dcol

            if not (0 <= next_row < R and 0 <= next_col < C):
                continue
            if visited[next_row][next_col]:
                continue
            if board[next_row][next_col] == '#':
                continue

            visited[next_row][next_col] = True
            fire_board[next_row][next_col] = level + 1
            queue.append(((next_row, next_col), level + 1))
    return fire_board


def solution(board: List[str], init_point: Tuple[int, int], fire_point_list: List[Tuple[int, int]]):
    R, C = len(board), len(board[0])
    fire_board = get_fire_board(board, fire_point_list, R, C)

    visited = [[False] * C for _ in range(R)]
    visited[init_point[0]][init_point[1]] = True
    queue = deque([(init_point, 0)])

    while queue:
        (cur_row, cur_col), level = queue.popleft()

        if cur_row == 0 or cur_row == R-1 or cur_col == 0 or cur_col == C-1:
            return level

        for drow, dcol in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_row = cur_row + drow
            next_col = cur_col + dcol

            if not (0 <= next_row < R and 0 <= next_col < C):
                continue
            if visited[next_row][next_col]:
                continue
            if board[next_row][next_col] == '#':
                continue
            if 0 <= fire_board[next_row][next_col] <= (level + 1):
                continue

            visited[next_row][next_col] = True
            queue.append(((next_row, next_col), level + 1))
    return -1


if __name__ == "__main__":
    R, C = list(map(int, input().split()))
    board = [input() for _ in range(R)]

    fire_point_list = []
    for row in range(R):
        for col in range(C):
            if board[row][col] == 'J':
                init_point = (row, col)
            elif board[row][col] == 'F':
                fire_point_list.append((row, col))

    time = solution(board, init_point, fire_point_list)
    if time < 0:
        print("IMPOSSIBLE")
    else:
        print(time+1)

'Algorithm > 백준' 카테고리의 다른 글

[BOJ] 15683: 감시  (0) 2026.03.25
[BOJ] 1941: 소문난 칠공주  (0) 2026.03.19
[BOJ] 1759: 암호 만들기  (0) 2026.03.18
[BOJ] 6593: 상범 빌딩  (1) 2026.03.16

티스토리툴바