가중치가 부여된 무방향 그래프가 하나 주어져 있다고 가정해 봅시다. 그래프에는 N개의 서로 다른 노드와 M개의 간선이 존재하며, 그중 일부 노드는 '좋은 노드(good node)'로 분류되어 있습니다. 우리가 구해야 하는 것은 서로 다른 두 좋은 노드로 이루어진 모든 쌍 가운데, 두 노드 사이의 거리가 가장 짧은 값입니다.
예를 들어 그래프에서 노란색으로 칠해진 노드들을 좋은 노드라고 생각해 보겠습니다. 좋은 노드 쌍과 그 사이의 거리가 각각 (1 → 3)은 11, (3 → 5)는 13, (1 → 5)는 24라면, 이 중 가장 작은 값인 11이 정답이 됩니다.
접근 방법
이 문제는 다익스트라(Dijkstra) 최단 경로 알고리즘을 응용하여 해결할 수 있습니다. 핵심 아이디어는 각 좋은 노드를 시작점으로 삼아 다익스트라 탐색을 수행하되, 두 번째 좋은 노드에 도달하는 순간 탐색을 조기에 종료하는 것입니다. 또한 현재까지 발견한 최솟값(result)보다 더 큰 거리의 노드를 큐에서 꺼내는 순간에도 탐색을 중단하여 불필요한 연산을 줄입니다.
구체적인 절차는 다음과 같습니다.
- N := 100005, MAX_VAL := 99999999로 상수를 설정합니다.
- 최소 힙 기반의 우선순위 큐 q를 생성하고, result := MAX_VAL로 초기화합니다.
- i := 1부터 n까지 반복합니다.
- good_verts[i]가 false이면 해당 노드는 좋은 노드가 아니므로 다음 반복으로 건너뜁니다.
- j := 1부터 n까지 dist[j] := MAX_VAL, vis[j] := 0으로 초기화합니다.
- dist[i] := 0으로 설정하고, 큐 q를 비운 뒤 {0, i}를 삽입합니다.
- good := 0으로 초기화합니다.
- 큐가 빌 때까지 다음을 반복합니다.
- v := 큐의 top 원소(노드 번호)를 확인하고 큐에서 제거합니다.
- vis[v]가 true이면 건너뜁니다.
- vis[v] := 1로 방문 표시를 하고, v가 좋은 노드이면 good을 1 증가시킵니다.
- dist[v] > result이면 이미 더 짧은 경로를 찾았으므로 루프를 탈출합니다.
- good == 2이고 v가 좋은 노드이면 result := min(result, dist[v])로 갱신한 뒤 루프를 탈출합니다.
- v에 인접한 모든 정점 (to, weight)에 대해 dist[v] + weight < dist[to]이면 dist[to]를 갱신하고 {dist[to], to}를 큐에 삽입합니다.
- 모든 반복이 끝나면 result를 반환합니다.
시간 복잡도
좋은 노드의 개수를 k라고 하면, 각 좋은 노드마다 한 번씩 다익스트라를 수행하므로 전체 시간 복잡도는 O(k · (N + M) log N)입니다. 다만 두 번째 좋은 노드를 만나거나 현재 최솟값보다 먼 노드가 나오면 즉시 종료하기 때문에, 실제 수행 시간은 이보다 훨씬 짧은 경우가 많습니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define MAX_VAL 99999999
void insert_edge(vector<pair<int, int> > graph[], int x, int y, int weight) {
graph[x].push_back({ y, weight });
graph[y].push_back({ x, weight });
}
int get_min_dist(vector<pair<int, int> > graph[], int n, int dist[], int vis[], int good_verts[], int k) {
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>> q;
int result = MAX_VAL;
for (int i = 1; i <= n; i++) {
if (!good_verts[i])
continue;
for (int j = 1; j <= n; j++) {
dist[j] = MAX_VAL;
vis[j] = 0;
}
dist[i] = 0;
while (!q.empty())
q.pop();
q.push({ 0, i });
int good = 0;
while (!q.empty()) {
int v = q.top().second;
q.pop();
if (vis[v])
continue;
vis[v] = 1;
good += good_verts[v];
if (dist[v] > result)
break;
if (good == 2 and good_verts[v]) {
result = min(result, dist[v]);
break;
}
for (int j = 0; j < graph[v].size(); j++) {
int to = graph[v][j].first;
int weight = graph[v][j].second;
if (dist[v] + weight < dist[to]) {
dist[to] = dist[v] + weight;
q.push({ dist[to], to });
}
}
}
}
return result;
}
int main() {
int n = 5, m = 5;
vector<pair<int, int> > graph[N];
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 2, 3, 4);
insert_edge(graph, 3, 4, 1);
insert_edge(graph, 4, 5, 8);
int k = 3;
int good_verts[N], vis[N], dist[N];
good_verts[1] = good_verts[3] = good_verts[5] = 1;
cout << get_min_dist(graph, n, dist, vis, good_verts, k);
}입력
n = 5, m = 5 insert_edge(graph, 1, 2, 3); insert_edge(graph, 2, 3, 4); insert_edge(graph, 3, 4, 1); insert_edge(graph, 4, 5, 8); k = 3 good_verts[1] = good_verts[3] = good_verts[5] = 1;
출력
7
노드 1, 3, 5가 좋은 노드일 때, 노드 1에서 3까지의 거리는 3 + 4 = 7, 노드 3에서 5까지의 거리는 4 + 1 + 8 = 13, 노드 1에서 5까지의 거리는 3 + 4 + 1 + 8 = 16입니다. 따라서 세 쌍 중 가장 짧은 거리인 7이 출력됩니다.