[Gold IV] 불 - 5427

문제 링크

성능 요약

메모리: 67772 KB, 시간: 2000 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 격자 그래프

문제 설명

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

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

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

입력

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

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

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

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

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

출력

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

---

문제 풀이

문제 분석

이 문제는 상근이가 불이 번지는 건물에서 탈출하는 최단 시간을 찾는 문제입니다. 건물은 빈 공간(.), 벽(#), 상근이의 시작 위치(@), 불의 시작 위치(*)로 구성된 격자 형태로 주어집니다. 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나가고, 상근이도 동서남북 인접한 빈 공간으로 이동할 수 있습니다. 상근이는 벽을 통과할 수 없고, 불이 붙었거나 현재 초에 불이 붙을 칸으로는 이동할 수 없습니다. 상근이가 건물 지도의 가장자리(경계)에 도달하면 탈출에 성공한 것으로 봅니다. 입력은 여러 개의 테스트 케이스로 주어지며, 각 테스트 케이스마다 건물의 너비와 높이, 그리고 지도가 주어집니다. 출력은 가장 빠른 탈출 시간 또는 탈출이 불가능할 경우 "IMPOSSIBLE"입니다.

접근 방법

이 문제는 최단 시간을 찾는 문제이므로, 너비 우선 탐색(BFS) 알고리즘을 사용하는 것이 가장 적합합니다. 하지만 단순히 상근이의 BFS만으로는 해결할 수 없습니다. 불도 동시에 확산되기 때문에, 불의 확산과 상근이의 이동을 시간 흐름에 맞춰 함께 시뮬레이션해야 합니다.

핵심 아이디어는 다음과 같습니다:

1. 시간 단위 시뮬레이션: 매 초마다 불의 확산과 상근이의 이동을 순차적으로 처리합니다.
2. 불 먼저 확산: 상근이가 이동할 칸을 결정하기 전에, 현재 초에 불이 어디까지 퍼질지 먼저 계산하여 지도에 반영해야 합니다. 상근이는 현재 초에 새로 불이 붙는 칸으로는 이동할 수 없기 때문입니다.
3. 두 개의 BFS 큐: 불의 위치를 관리하는 큐와 상근이의 위치(및 이동 시간)를 관리하는 큐를 별도로 사용하여 각각의 BFS를 진행합니다.
4. 방문 여부 확인: 상근이가 이미 방문했던 칸은 다시 방문하지 않도록 visited 배열을 사용하여 중복 탐색을 방지하고 최단 경로를 보장합니다.

구현 설명

1. 초기 설정 및 지도 파싱

• directions: 상하좌우 이동을 위한 튜플 리스트 [(1,0),(-1,0),(0,1),(0,-1)]를 정의합니다.
• 각 테스트 케이스마다:
  • 지도의 너비 m과 높이 n을 읽고, graph (지도 상태)와 visited (상근이 방문 여부) 배열을 초기화합니다.
  • 지도 정보를 읽으면서 *는 fires 덱에, @는 상근이의 시작점으로 간주하여 graph에서는 .으로 바꾸고 visited를 True로 설정한 후 (x, y, 1) (위치, 시작 시간 1) 형태로 queue 덱에 추가합니다.

2. 불 확산 (fire 함수)

• fire(graph, fires) 함수는 현재 초에 불이 붙은 모든 칸(fires 덱에 있는 칸)으로부터 다음 초에 불이 붙을 칸을 계산합니다.
• 새로운 불의 위치를 저장할 new_fires 덱을 생성합니다.
• fires 덱에 있는 각 불의 위치 (x, y)에 대해 4방향을 탐색합니다.
• 탐색한 인접 칸 (sx, sy)가 지도 범위 내에 있고 아직 불이 붙지 않은 빈 공간(graph[sx][sy] == ".")이라면:
  • 해당 칸에 불을 표시(graph[sx][sy] = "*")하고,
  • new_fires 덱에 추가합니다.
• new_fires 덱을 반환하여 다음 초의 불 확산 시작점으로 사용합니다.

3. 상근이 이동 (move 함수)

• move(graph, visited, queue) 함수는 현재 초에 상근이가 위치한 모든 칸(queue 덱에 있는 칸)으로부터 다음 초에 이동할 칸을 계산합니다.
• 새로운 상근이의 위치를 저장할 new_queue 덱을 생성합니다.
• queue 덱에 있는 각 상근이의 위치 (x, y, cnt)에 대해:
  • 탈출 조건 확인: 만약 (x, y)가 지도의 경계(0행, n-1행, 0열, m-1열 중 하나)에 있다면, 상근이가 탈출한 것이므로 현재 시간 cnt를 출력하고 None을 반환하여 메인 루프를 종료합니다.
  • 4방향을 탐색합니다.
  • 탐색한 인접 칸 (sx, sy)가 지도 범위 내에 있고, 상근이가 아직 방문하지 않았으며(not visited[sx][sy]), 벽이나 불이 아닌 빈 공간(graph[sx][sy] == ".")이라면:
    • new_queue 덱에 (sx, sy, cnt+1)을 추가합니다 (시간 cnt가 1 증가).
    • visited[sx][sy]를 True로 표시합니다.
• queue 덱의 모든 요소를 처리한 후, 만약 new_queue가 비어있다면 상근이가 더 이상 이동할 곳이 없다는 의미이므로 "IMPOSSIBLE"을 출력합니다.
• new_queue 덱을 반환하여 다음 초의 상근이 이동 시작점으로 사용합니다.

4. 메인 루프 (시간 진행)

• while True 루프를 통해 매 초 시뮬레이션을 진행합니다.
• 루프 내에서:
  1. fires = fire(graph, fires): 불을 먼저 확산시킵니다. graph가 업데이트됩니다.
  2. queue = move(graph, visited, queue): 불이 확산된 후 상근이를 이동시킵니다. 이 함수는 탈출 성공 시 시간을 출력하고 None을 반환하거나, 이동 불가능 시 "IMPOSSIBLE"을 출력한 후 비어있는 덱을 반환할 수 있습니다.
  3. if not queue:: move 함수가 None을 반환했거나 (None은 False로 평가됨), 상근이의 new_queue가 비어있다면, 더 이상 시뮬레이션을 진행할 필요가 없으므로 루프를 종료합니다.

⏱복잡도 분석

• 시간 복잡도: O(T * N * M)

  • T: 테스트 케이스의 개수 (최대 100).
  • N * M: 지도의 크기 (최대 1000 * 1000 = 10^6).
  • BFS의 특성상, 각 칸은 불 또는 상근이에 의해 최대 한 번씩 탐색됩니다. 매 초마다 fire 함수와 move 함수는 해당 큐에 있는 모든 위치를 한 번씩 처리하며, 각 위치당 4방향을 탐색합니다 (상수 시간). 최악의 경우, 불이나 상근이가 모든 칸을 방문해야 할 수 있습니다. 따라서 하나의 테스트 케이스에 대한 전체 시간 복잡도는 O(N * M)이 됩니다.
  • 총 시간 복잡도는 T개의 테스트 케이스를 모두 처리하므로 O(T * N * M)입니다. 최대 100 * 10^6 = 10^8 연산으로, 2초의 시간 제한 내에서 충분히 수행될 수 있습니다.

• 공간 복잡도: O(N * M)

  • graph: 지도를 저장하는 2차원 리스트로 O(N * M) 공간을 사용합니다.
  • visited: 상근이의 방문 여부를 저장하는 2차원 리스트로 O(N * M) 공간을 사용합니다.
  • fires 덱: 모든 칸이 동시에 불에 붙을 수 있는 최악의 경우 O(N * M) 공간을 사용할 수 있습니다.
  • queue 덱: 상근이가 동시에 여러 경로로 같은 거리에 도달할 수 있는 최악의 경우 O(N * M) 공간을 사용할 수 있습니다.
  • 따라서 전체 공간 복잡도는 O(N * M)입니다.

핵심 포인트

1. 불-상근이 행동 순서: 매 초마다 불이 먼저 확산하여 지도(graph)를 업데이트한 후, 상근이가 업데이트된 지도 정보를 기반으로 이동 가능한지 판단해야 합니다. 이 순서가 바뀌면 상근이가 이미 불이 붙은 칸으로 이동할 수 있게 되어 오답이 발생합니다.
2. 두 개의 BFS 큐: 불의 확산과 상근이의 이동을 별도의 BFS 큐(fires와 queue)로 관리하면서 시간 흐름에 맞춰 단계적으로 처리합니다. deque는 양방향 큐이므로 BFS에 효율적입니다.
3. 경계 탈출 조건 및 불가능 처리: 상근이가 지도의 가장자리(0번째 행/열 또는 마지막 행/열)에 도달하면 탈출 성공으로 간주합니다. 만약 상근이의 큐가 비어 더 이상 이동할 수 없는데도 탈출하지 못했다면, 탈출 불가능으로 판단합니다.

풀이 코드

import sys
from collections import deque

directions = [(1,0),(-1,0),(0,1),(0,-1)]

def fire(graph, fires):
    new_fires = deque()
    while fires:
        x,y = fires.popleft()
        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<=sx<n and 0<=sy<m and graph[sx][sy] == ".":
                graph[sx][sy] = "*"
                new_fires.append((sx,sy))

    return new_fires

def move(graph, visited, queue):
    new_queue = deque()    
    while queue:
        x,y,cnt = queue.popleft()
        if x == n-1 or y == m-1 or x == 0 or y == 0:
            print(cnt)
            return None
        
        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<= sx < n and 0<= sy < m and not visited[sx][sy] and graph[sx][sy] == ".":
                new_queue.append((sx,sy,cnt+1))
                visited[sx][sy] = True

    if not new_queue:
        print("IMPOSSIBLE")

    return new_queue

t = int(sys.stdin.readline())

for i in range(t):
    graph = []
    m,n = map(int, sys.stdin.readline().split())
    visited = [[False]*m for i in range(n)]

    for i in range(n):
        graph.append(list(sys.stdin.readline().strip()))

    fires = deque()
    
    queue = deque()
    for i in range(n):
        for j in range(m):
            if graph[i][j] == "*":
                fires.append((i,j))
            
            elif graph[i][j] == "@":
                graph[i][j] = "."
                visited[i][j] = True
                queue.append((i,j,1)) 

    while True:
        fires = fire(graph, fires)
        queue = move(graph,visited, queue)

        if not queue:
            break