메모리: 67772 KB, 시간: 2000 ms
그래프 이론, 그래프 탐색, 너비 우선 탐색, 격자 그래프
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
각 지도에 @의 개수는 하나이다.
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
이 문제는 상근이가 불이 번지는 건물에서 탈출하는 최단 시간을 찾는 문제입니다. 건물은 빈 공간(.), 벽(#), 상근이의 시작 위치(@), 불의 시작 위치(*)로 구성된 격자 형태로 주어집니다. 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나가고, 상근이도 동서남북 인접한 빈 공간으로 이동할 수 있습니다. 상근이는 벽을 통과할 수 없고, 불이 붙었거나 현재 초에 불이 붙을 칸으로는 이동할 수 없습니다. 상근이가 건물 지도의 가장자리(경계)에 도달하면 탈출에 성공한 것으로 봅니다. 입력은 여러 개의 테스트 케이스로 주어지며, 각 테스트 케이스마다 건물의 너비와 높이, 그리고 지도가 주어집니다. 출력은 가장 빠른 탈출 시간 또는 탈출이 불가능할 경우 "IMPOSSIBLE"입니다.
이 문제는 최단 시간을 찾는 문제이므로, 너비 우선 탐색(BFS) 알고리즘을 사용하는 것이 가장 적합합니다. 하지만 단순히 상근이의 BFS만으로는 해결할 수 없습니다. 불도 동시에 확산되기 때문에, 불의 확산과 상근이의 이동을 시간 흐름에 맞춰 함께 시뮬레이션해야 합니다.
핵심 아이디어는 다음과 같습니다:
visited 배열을 사용하여 중복 탐색을 방지하고 최단 경로를 보장합니다.directions: 상하좌우 이동을 위한 튜플 리스트 [(1,0),(-1,0),(0,1),(0,-1)]를 정의합니다.m과 높이 n을 읽고, graph (지도 상태)와 visited (상근이 방문 여부) 배열을 초기화합니다.*는 fires 덱에, @는 상근이의 시작점으로 간주하여 graph에서는 .으로 바꾸고 visited를 True로 설정한 후 (x, y, 1) (위치, 시작 시간 1) 형태로 queue 덱에 추가합니다.fire 함수)fire(graph, fires) 함수는 현재 초에 불이 붙은 모든 칸(fires 덱에 있는 칸)으로부터 다음 초에 불이 붙을 칸을 계산합니다.new_fires 덱을 생성합니다.fires 덱에 있는 각 불의 위치 (x, y)에 대해 4방향을 탐색합니다.(sx, sy)가 지도 범위 내에 있고 아직 불이 붙지 않은 빈 공간(graph[sx][sy] == ".")이라면:
graph[sx][sy] = "*")하고,new_fires 덱에 추가합니다.new_fires 덱을 반환하여 다음 초의 불 확산 시작점으로 사용합니다.move 함수)move(graph, visited, queue) 함수는 현재 초에 상근이가 위치한 모든 칸(queue 덱에 있는 칸)으로부터 다음 초에 이동할 칸을 계산합니다.new_queue 덱을 생성합니다.queue 덱에 있는 각 상근이의 위치 (x, y, cnt)에 대해:
(x, y)가 지도의 경계(0행, n-1행, 0열, m-1열 중 하나)에 있다면, 상근이가 탈출한 것이므로 현재 시간 cnt를 출력하고 None을 반환하여 메인 루프를 종료합니다.(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 덱을 반환하여 다음 초의 상근이 이동 시작점으로 사용합니다.while True 루프를 통해 매 초 시뮬레이션을 진행합니다.fires = fire(graph, fires): 불을 먼저 확산시킵니다. graph가 업데이트됩니다.queue = move(graph, visited, queue): 불이 확산된 후 상근이를 이동시킵니다. 이 함수는 탈출 성공 시 시간을 출력하고 None을 반환하거나, 이동 불가능 시 "IMPOSSIBLE"을 출력한 후 비어있는 덱을 반환할 수 있습니다.if not queue:: move 함수가 None을 반환했거나 (None은 False로 평가됨), 상근이의 new_queue가 비어있다면, 더 이상 시뮬레이션을 진행할 필요가 없으므로 루프를 종료합니다.시간 복잡도: O(T * N * M)
T: 테스트 케이스의 개수 (최대 100).N * M: 지도의 크기 (최대 1000 * 1000 = 10^6).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) 공간을 사용할 수 있습니다.graph)를 업데이트한 후, 상근이가 업데이트된 지도 정보를 기반으로 이동 가능한지 판단해야 합니다. 이 순서가 바뀌면 상근이가 이미 불이 붙은 칸으로 이동할 수 있게 되어 오답이 발생합니다.fires와 queue)로 관리하면서 시간 흐름에 맞춰 단계적으로 처리합니다. deque는 양방향 큐이므로 BFS에 효율적입니다.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