문제 요약
발전소는 1층부터 h층까지 존재한다.
각 층은 모두 같은 구조의 n x m 격자로 이루어져 있다.
격자의 각 칸은 다음 중 하나다.
.: 이동할 수 있는 통로#: 이동할 수 없는 폐쇄 구역@: 엘리베이터
기술자는 상하좌우로 한 칸 이동할 때마다 1초를 사용한다.
다른 층으로 이동하려면 반드시 엘리베이터를 이용해야 하며, 한 층을 이동할 때마다 1초가 걸린다.
격자에는 1번부터 k번까지의 회로 패널이 있다.
기술자는 항상 1번 패널이 있는 위치에서 출발하지만, 1번 패널의 선행 조건이 만족되지 않았다면 바로 활성화할 수 없다.
또한 [a, b]라는 안전 순서가 주어졌다면, b번 패널을 활성화하기 전에 a번 패널을 먼저 활성화해야 한다.
모든 패널을 안전하게 활성화하는 데 필요한 최소 시간을 구해야 한다.
핵심 아이디어
이 문제는 크게 두 단계로 나눌 수 있다.
- 패널 사이의 최단 이동 시간 계산
- 안전 순서를 만족하는 최소 활성화 순서 계산
격자의 실제 이동은 BFS로 처리하고, 패널 활성화 순서는 비트마스크 DP로 처리한다.
격자 이동 거리 계산: BFS
패널 방문 순서 계산: 비트마스크 DP패널 수는 최대 15개이므로 모든 활성화 상태를 비트마스크로 표현할 수 있다.
2^15 = 32,768따라서 각 활성화 상태와 현재 위치를 DP 상태로 사용하면 충분히 해결할 수 있다.
1. 패널 사이의 이동 시간 계산
각 층의 격자 구조는 모두 같다.
따라서 한 층 안에서 두 좌표 사이의 최단 거리는 층 번호와 관계없이 동일하다.
패널 i에서 패널 j로 이동하는 경우는 두 가지로 나뉜다.
같은 층에 있는 경우
두 패널이 같은 층에 있다면 격자 안에서 직접 이동하면 된다.
distance(i, j) = 두 패널 좌표 사이의 격자 최단 거리이 거리는 BFS로 구할 수 있다.
서로 다른 층에 있는 경우
다른 층으로 이동하려면 반드시 엘리베이터를 이용해야 한다.
따라서 이동 시간은 다음 세 부분의 합이다.
패널 i에서 엘리베이터까지 이동
+ 층 사이 이동
+ 엘리베이터에서 패널 j까지 이동수식으로 표현하면 다음과 같다.
distance(i, j)
= distance(i, elevator)
+ abs(floor[i] - floor[j])
+ distance(elevator, j)예를 들어 2층 패널에서 5층 패널로 이동한다면 엘리베이터에서 층을 이동하는 시간은 다음과 같다.
|2 - 5| = 3초BFS를 몇 번 실행해야 할까?
패널은 최대 15개다.
각 패널의 좌표에서 BFS를 한 번씩 실행하면 다음 정보를 모두 구할 수 있다.
- 해당 패널에서 다른 모든 패널 좌표까지의 거리
- 해당 패널에서 엘리베이터까지의 거리
따라서 BFS는 최대 k번만 실행하면 된다.
격자 크기는 최대 40 x 40이므로 충분히 빠르다.
2. 선행 조건을 비트마스크로 표현하기
각 패널을 하나의 비트로 표현한다.
패널이 4개라면 다음과 같이 나타낼 수 있다.
0000: 활성화된 패널 없음
0001: 1번 패널 활성화
0010: 2번 패널 활성화
0100: 3번 패널 활성화
1000: 4번 패널 활성화예를 들어 1번과 3번 패널이 활성화되어 있다면 다음과 같다.
0101각 패널의 선행 조건도 비트마스크로 저장한다.
required = [0] * k
for a, b in seqs:
required[b - 1] |= 1 << (a - 1)만약 2번 패널을 활성화하기 전에 1번과 3번 패널이 필요하다면 다음과 같이 저장된다.
required[1] = 0101패널 활성화 가능 여부
현재 활성화 상태가 mask일 때 next_panel을 활성화하려면 해당 패널의 모든 선행 조건이 mask에 포함되어 있어야 한다.
required[next_panel] & mask == required[next_panel]또는 다음처럼 이해할 수 있다.
필요한 패널 중 현재 활성화되지 않은 패널이 없어야 한다.DP 정의
다음과 같이 DP를 정의한다.
dp[mask][last]의미는 다음과 같다.
mask에 포함된 패널들을 활성화했고,
현재 last번 패널 위치에 있을 때의 최소 이동 시간mask는 활성화된 패널 집합이고, last는 기술자의 현재 위치를 나타낸다.
초기 상태
기술자는 항상 1번 패널 위치에서 출발한다.
하지만 1번 패널이 처음부터 활성화된 것은 아니다.
따라서 활성화된 패널이 없는 상태에서 기술자의 위치만 1번 패널로 설정한다.
dp[0][0] = 0여기서 last = 0은 1번 패널의 위치를 의미한다.
mask = 0이므로 아직 활성화된 패널은 없다.
만약 1번 패널에 선행 조건이 없다면, 이동 시간 0으로 바로 활성화할 수 있다.
반대로 선행 조건이 있다면 다른 패널로 먼저 이동해야 한다.
DP 전이
현재 상태가 다음과 같다고 하자.
dp[mask][last]아직 활성화하지 않은 next_panel 중 선행 조건이 만족된 패널을 선택한다.
if mask & (1 << next_panel):
continue
if required[next_panel] & mask != required[next_panel]:
continue이동 후 새로운 상태는 다음과 같다.
next_mask = mask | (1 << next_panel)최소 시간은 다음과 같이 갱신한다.
dp[next_mask][next_panel] = min(
dp[next_mask][next_panel],
dp[mask][last] + distance[last][next_panel],
)최종 답
모든 패널이 활성화된 비트마스크는 다음과 같다.
full_mask = (1 << k) - 1마지막에 어느 패널 위치에 있는지는 상관없다.
따라서 모든 마지막 위치 중 최솟값을 반환한다.
min(dp[full_mask])전체 코드
from collections import deque
def solution(h, grid, panels, seqs):
n = len(grid)
m = len(grid[0])
k = len(panels)
elevator_row = -1
elevator_col = -1
for row in range(n):
for col in range(m):
if grid[row][col] == "@":
elevator_row = row
elevator_col = col
floors = []
positions = []
for floor, row, col in panels:
floors.append(floor)
positions.append((row - 1, col - 1))
directions = [
(-1, 0),
(1, 0),
(0, -1),
(0, 1),
]
panel_distance = [[0] * k for _ in range(k)]
elevator_distance = [0] * k
for start in range(k):
start_row, start_col = positions[start]
distance = [[-1] * m for _ in range(n)]
distance[start_row][start_col] = 0
queue = deque([(start_row, start_col)])
while queue:
row, col = queue.popleft()
for dr, dc in directions:
next_row = row + dr
next_col = col + dc
if not (0 <= next_row < n and 0 <= next_col < m):
continue
if grid[next_row][next_col] == "#":
continue
if distance[next_row][next_col] != -1:
continue
distance[next_row][next_col] = distance[row][col] + 1
queue.append((next_row, next_col))
elevator_distance[start] = distance[elevator_row][elevator_col]
for target in range(k):
target_row, target_col = positions[target]
panel_distance[start][target] = distance[target_row][target_col]
move_time = [[0] * k for _ in range(k)]
for start in range(k):
for target in range(k):
if floors[start] == floors[target]:
move_time[start][target] = panel_distance[start][target]
else:
move_time[start][target] = (
elevator_distance[start]
+ abs(floors[start] - floors[target])
+ elevator_distance[target]
)
required = [0] * k
for a, b in seqs:
required[b - 1] |= 1 << (a - 1)
state_count = 1 << k
infinity = 10**18
dp = [[infinity] * k for _ in range(state_count)]
# 기술자는 1번 패널의 위치에서 출발하지만,
# 아직 어떤 패널도 활성화하지 않은 상태다.
dp[0][0] = 0
for mask in range(state_count):
for last in range(k):
current_time = dp[mask][last]
if current_time == infinity:
continue
for next_panel in range(k):
bit = 1 << next_panel
if mask & bit:
continue
if required[next_panel] & mask != required[next_panel]:
continue
next_mask = mask | bit
next_time = current_time + move_time[last][next_panel]
if next_time < dp[next_mask][next_panel]:
dp[next_mask][next_panel] = next_time
full_mask = state_count - 1
return min(dp[full_mask])시간 복잡도
격자의 칸 수를 V = n x m, 패널 수를 k라고 하자.
BFS
각 패널에서 BFS를 한 번씩 실행한다.
O(k x n x m)비트마스크 DP
활성화 상태는 2^k개이고, 각 상태에서 현재 위치와 다음 패널을 확인한다.
O(2^k x k^2)따라서 전체 시간 복잡도는 다음과 같다.
O(k x n x m + 2^k x k^2)제한사항에서 k <= 15, n, m <= 40이므로 충분히 처리할 수 있다.
공간 복잡도
BFS 거리 배열은 다음 크기를 사용한다.
O(n x m)DP 배열은 다음 크기를 사용한다.
O(2^k x k)따라서 전체 공간 복잡도는 다음과 같다.
O(n x m + 2^k x k)정리
이 문제는 격자 최단 거리와 순서 제약이 함께 등장한다.
두 문제를 한 번에 해결하려고 하면 복잡하지만, 다음과 같이 분리하면 깔끔하게 해결할 수 있다.
- BFS로 패널 사이의 최단 이동 시간을 미리 계산한다.
- 안전 순서를 비트마스크로 저장한다.
dp[mask][last]로 최소 활성화 시간을 계산한다.
핵심 포인트는 다음과 같다.
- 다른 층으로 이동할 때는 반드시 엘리베이터를 거친다.
- 기술자는 1번 패널 위치에서 출발하지만 1번 패널이 활성화된 상태는 아니다.
- 패널의 선행 조건이 모두 만족된 경우에만 다음 DP 상태로 이동할 수 있다.
- 패널 수가 최대 15개이므로 비트마스크 DP를 사용할 수 있다.
격자 이동은 BFS, 방문 순서 최적화는 비트마스크 DP로 역할을 분리하는 것이 이 문제의 핵심이다.
