백준 - 불! / Gold 5 / 4179번 / Python

문제 📋

백준 - 불!

풀이 📝

import sys
from collections import deque


def solution(miro):
    time = 0
    delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    j_visited = [[False] * c for _ in range(r)]
    j_q = deque()
    fire_q = deque()

    for i in range(r):
        for j in range(c):
            if miro[i][j] == 'J':
                miro[i][j] = '.'
                j_q.append((i, j))
            elif miro[i][j] == 'F':
                fire_q.append((i, j))

    while j_q:  # 지훈이가 갈 곳이 있다면
        for _ in range(len(fire_q)):  # 먼저 불 확산.
            row, col = fire_q.popleft()

            for i in range(4):
                delta_row, delta_col = delta[i]
                new_row = row + delta_row
                new_col = col + delta_col

                if new_row < 0 or new_row >= r or new_col < 0 or new_col >= c:
                    continue

                if miro[new_row][new_col] == '.':
                    miro[new_row][new_col] = 'F'
                    fire_q.append((new_row, new_col))

        for _ in range(len(j_q)):  # BFS로 지훈이가 다음 타임에 갈 방향 탐색.
            row, col = j_q.popleft()

            for i in range(4):
                delta_row, delta_col = delta[i]
                new_row = row + delta_row
                new_col = col + delta_col

                if new_row < 0 or new_row >= r or new_col < 0 or new_col >= c:  # 경계 지점에 있으면 다음 타임에 탈출 확정.
                    return time + 1

                if not j_visited[new_row][new_col] and miro[new_row][new_col] == '.':
                    j_visited[new_row][new_col] = True
                    j_q.append((new_row, new_col))
        time += 1

    # 갈 곳이 더이상 없다면
    return "IMPOSSIBLE"


r, c = map(int, sys.stdin.readline().split())
miro = [list(sys.stdin.readline().rstrip()) for _ in range(r)]

print(solution(miro))

1. 문제 정의
   2차원 격자의 미로에서 지훈이와 불이 1초마다 1칸씩 상하좌우로 움직일 때
   지훈이가 불을 피해 탈출할 수 있는 최단거리를 구하는 문제이다.

2. 시간 복잡도 계산
   최단거리 문제이기 때문에 BFS 탐색을 떠올렸으며
   최악의 경우 BFS러 전부 탐색할 경우 시간초과가 나지 않을 지 확인해야한다.

   행과 열의 개수가 각각 최대 1,000이기 때문에 전체 탐색 범위는
   최대 1,000,000이므로 최악의 경우에도 시간초과가 나지 않을것이라 판단했다.

3. 문제 풀이
   먼저 불을 퍼트려서 갈 수 있는 길들을 비활성화 시키고
   지훈이는 ' . '인 곳만 가도록 BFS로 구현했다.

   이렇게 구현해도 문제 없는 이유는 불 기준으로 상하좌우에 있는 길들은
   지훈이가 먼저 이동한다 생각해도 다음턴에 불에 바로 삼켜지기 때문이다.

   ps. (처음엔 지훈이가 움직이는 BFS와 불이 움직이는 BFS를 함수로 따로 구현하려 시도했다. 하지만 각각 한 Breadth씩 순서대로 나가야 하기 때문에 하나의 함수에 구현하게 되었다.)

4. 예외 사항
   F가 시작 지점이 여러 개일 수도 있다.