문제 정의
상황:
- H층 건물의 발전소 정전 발생
- 기술자가 엘리베이터와 통로를 이용해 K개의 회로 패널을 주어진 '안전 순서'에 맞게 모두 활성화하는 최소 시간을 구하기
제약 조건:
- 격자 크기 와 층수
- 안전 순서
- 패널의 개수
안전 순서 : A 패널을 켜야 B 패널을 켤 수 있다는 명확한 의존성이 존재합니다. 위상 정렬(Topological Sort)이 필요함을 암시합니다.
패널의 개수 : 이 문제의 가장 핵심적인 힌트입니다.
패널이 15개 이하라는 것은, 모든 순열()을 탐색하면 시간 초과가 나지만,
비트마스킹을 활용한 DP ()를 사용하면 통과할 수 있다는 뜻입니다.
(전형적인 외판원 순회 - TSP 문제의 조건)
접근 방법
1. 공간과 시간의 분리: 모든 패널 간 최단 거리 전처리 (BFS)
DFS를 수행하면서 매번 거리를 계산할 경우,
시간 복잡도는 으로 매우 비효율적입니다.
따라서 DFS를 시작하기 전에, 번 ~ 번 패널 사이의 모든 이동 거리를 미리 계산하여
2차원 배열 panelDist[K+1][K+1]에 캐싱해야 합니다.
패널 간 이동은 다음 두 가지 경우를 고려해야 합니다.
-
다른 층 이동
→ 시작 패널 → 엘리베이터 → 층 이동 → 엘리베이터 → 도착 패널 -
같은 층 이동
→ 두 가지 경로 중 더 짧은 거리 선택
Step 2. 위상 정렬 (Topological Sort)
패널 간의 선후 관계는 방향 그래프인 graph와
진입 차수 배열인 in을 통해 관리합니다.
현재 활성화 가능한 패널은 진입 차수가 0인 패널입니다.
탐색 과정에서는 다음과 같이 의존성을 관리합니다.
특정 패널을 활성화하면 → 연결된 다음 패널들의 진입 차수를 감소(-1)
백트래킹 시 → 다시 진입 차수를 복구(+1)
이를 통해 동적으로 위상 정렬을 유지하면서 탐색할 수 있습니다.
Step 3. 최적 경로 탐색: TSP 기반 비트마스킹 DP
- 패널 간 이동 거리 →
panelDist에서 에 조회 가능 - 방문 가능 여부 → 으로 제어 가능
따라서 문제는 다음과 같이 변환됩니다.
“순서 제약을 만족하면서 모든 패널을 최소 비용으로 방문하는 문제”
이는 전형적인 TSP(외판원 순회 문제) 형태로 볼 수 있고
비트마스킹 DP를 통해 해결했습니다.
코드
import java.util.*;
class Node {
int v;
Node node;
public Node (int v, Node node) {
this.v = v;
this.node = node;
}
}
class Solution {
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};
static final int MAX = 10000000;
static int n, m, k, posX, posY;
static int[][] dist;
static int[][] panelDist;
static Node[] graph;
static int[] in;
static String[] grid;
static int[][] panels;
static int[][] seqs;
static boolean[][] visited;
static int min;
static int[][] dp;
public int solution(int h, String[] g, int[][] p, int[][] s) {
init(h, g, p, s);
setElevatorPos();
setDistFromElevator();
setPanelDist();
setGraph();
return getAnswer();
}
static void dfs(int currentDist, int count, int u, int bitmask) {
if (count == k) {
min = Math.min(min, currentDist);
return;
}
if (min <= currentDist) return;
if (dp[bitmask][u] <= currentDist) return;
dp[bitmask][u] = currentDist;
for (int v = 1; v <= k; v++) {
if (in[v] == 0 && (bitmask & (1 << v)) == 0) {
for (Node node = graph[v]; node != null; node = node.node) {
in[node.v]--;
}
dfs(currentDist + panelDist[u][v], count + 1, v, bitmask | (1 << v));
for (Node node = graph[v]; node != null; node = node.node) {
in[node.v]++;
}
}
}
}
static void setElevatorPos() {
for (int i = 0; i < n; i++) {
String str = grid[i];
for (int j = 0; j < m; j++) {
if (str.charAt(j) == '@') {
posY = i;
posX = j;
break;
}
}
}
}
static void setDistFromElevator() {
dist = new int[n][m];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], MAX);
}
dist[posY][posX] = 0;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{posY, posX});
while (!q.isEmpty()) {
int[] node = q.poll();
int y = node[0];
int x = node[1];
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (0 <= ny && ny < n && 0 <= nx && nx < m && grid[ny].charAt(nx) != '#' && dist[ny][nx] == MAX) {
dist[ny][nx] = dist[y][x] + 1;
q.offer(new int[]{ny, nx});
}
}
}
}
static void setPanelDist() {
panelDist = new int[k+1][k+1];
for (int i = 1; i <= k; i++) {
for (int j = i + 1; j <= k; j++) {
panelDist[i][j] = getDist(i, j);
panelDist[j][i] = panelDist[i][j];
}
}
}
static void setGraph() {
in = new int[k+1];
graph = new Node[k+1];
for (int[] seq : seqs) {
int u = seq[0];
int v = seq[1];
graph[u] = new Node(v, graph[u]);
in[v]++;
}
}
static int getDist(int u, int v) {
if (u == v) return 0;
int[] uInfo = panels[u-1];
int[] vInfo = panels[v-1];
int uY = uInfo[1]-1, uX = uInfo[2]-1, uF = uInfo[0];
int vY = vInfo[1]-1, vX = vInfo[2]-1, vF = vInfo[0];
if (uF == vF) {
return bfs(uY, uX, vY, vX);
}
return dist[uY][uX] + dist[vY][vX] + Math.abs(uF - vF);
}
static int bfs(int sy, int sx, int ey, int ex) {
if (sy == ey && sx == ex) return 0;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sy, sx, 0});
for (int i = 0; i < n; i++) {
Arrays.fill(visited[i], false);
}
visited[sy][sx] = true;
while(!q.isEmpty()) {
int[] node = q.poll();
int y = node[0];
int x = node[1];
int d = node[2];
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (0 <= ny && ny < n && 0 <= nx && nx < m && !visited[ny][nx] && grid[ny].charAt(nx) != '#') {
if (ny == ey && nx == ex) {
return d + 1;
}
visited[ny][nx] = true;
q.offer(new int[]{ny, nx, d + 1});
}
}
}
return MAX;
}
static void init(int h, String[] g, int[][] p, int[][] s) {
grid = g;
panels = p;
seqs = s;
n = grid.length;
m = grid[0].length();
k = panels.length;
visited = new boolean[n][m];
dp = new int[1 << (k + 1)][k + 1];
for(int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], MAX);
}
}
static int getAnswer() {
min = MAX;
for (int v = 1; v <= k; v++) {
if (in[v] == 0) {
int bitmask = (1 << v);
for (Node node = graph[v]; node != null; node = node.node) {
in[node.v]--;
}
dfs(panelDist[1][v], 1, v, bitmask);
for (Node node = graph[v]; node != null; node = node.node) {
in[node.v]++;
}
}
}
return min;
}
}
while True: study()