https://www.acmicpc.net/problem/2211
[필자 사고]
최단거리 루트.. 뭐다?? 다익스트라 알고리즘이다. 다만 이 문제에서 요구하는 거는 역추적
즉 해당 회선 경로까지 추출해야 된다는 점이다.
그래서 필자는 parent를 이용하여 부모노드 까지 기록을 해주었다.
아래는 자세한 코드 해설이다.
[코드 해설]
문제 핵심 요약
- 1번 컴퓨터가 슈퍼컴퓨터.
- 네트워크를 “최소 개수의 회선”으로 복구하되, 1번에서 각 컴퓨터까지의 최단 통신 시간은 기존과 동일해야 함.
- 즉, 1번을 루트로 하는 최단경로 트리(Shortest Path Tree, SPT) 를 복구하면 두 조건을 동시에 만족:
- 트리는 간선 수가 정확히 N-1 → “최소 회선”
- 다익스트라로 얻은 최단거리 기반 트리 → “최단 시간 유지”
아이디어 한 줄 정리
1번에서 다익스트라를 돌리며 parent[v](v로 가는 최단경로 상의 직전 정점)를 저장.
마지막에 v = 2..N에 대해 (parent[v], v)를 출력하면 된다. 이 간선 집합이 곧 복구해야 할 회선 목록이다.
코드 구조 해설 (제공하신 코드 기준)
그래프 표현
struct Node {
int value; // 간선 가중치
int to; // 도착 정점
};
vector<vector<Node>> arr; // 인접 리스트
- arr[u]는 정점 u에서 나가는 간선 목록.
- 각 간선은 (to, value)로 저장.
입력
cin >> N >> M;
arr.resize(N + 1);
for (int i = 0; i < M; i++) {
int start, end, value;
cin >> start >> end >> value;
arr[start].push_back({value, end});
arr[end].push_back({value, start});
}
- 양방향 가중치 그래프를 구성.
우선순위 큐(최소 힙) 비교자
struct cmp {
bool operator()(Node a, Node b) {
return a.value > b.value;
}
};
- value(여기서는 “현재까지의 누적 거리”)가 작은 것이 먼저 나오도록 하는 최소 힙.
다익스트라 핵심(BFS라는 이름이지만 실제로는 다익스트라)
priority_queue<Node, vector<Node>, cmp> pq;
pq.push({0, 1}); // (거리 0, 시작점 1)
vector<int> dist(N + 1, 987654321);
vector<int> parent(N + 1, -1);
dist[1] = 0;
while (!pq.empty()) {
int value = pq.top().value; // 지금 꺼낸 경로의 누적 거리
int to = pq.top().to; // 지금 위치한 정점
pq.pop();
for (Node node : arr[to]) {
int nextNode = node.to;
int nextValue = node.value + value; // to까지의 거리 + (to→nextNode 간선 가중치)
if (nextValue < dist[nextNode]) {
dist[nextNode] = nextValue;
parent[nextNode] = to; // 최단경로 상의 직전 정점 갱신
pq.push({ nextValue, nextNode });
}
}
}
- 전형적인 다익스트라 구현.
- parent[nextNode] = to로 “최단경로 트리”를 동시에 복원한다.
출력(복구해야 할 회선)
cout << N - 1 << "\n";
for (int v = 2; v <= N; v++) {
cout << parent[v] << " " << v << "\n";
}
- 트리의 간선 수는 항상 N-1.
- 각 노드 v(2..N)에 대해 (parent[v], v)를 출력.
- 스페셜 저지이므로 순서는 자유롭다.
왜 이것이 정답인가?
- 최소 회선: 모든 노드가 통신 가능하려면 그래프가 연결되어야 한다.
연결 그래프 중 간선 수가 최소인 구조는 트리이며 간선 수는 항상 N-1. - 최단 시간 유지: 1번에서 각 노드까지의 최단 거리를 보존하려면, 각 노드로 가는 최단경로 중에서 간선 하나씩만 선택하면 된다.
다익스트라의 parent[]가 바로 그 간선들을 가리키므로, 해당 간선들만 복구해도 모든 노드의 최단거리는 기존과 동일하다.
복잡도
- 시간: O((N + M) log N) (우선순위 큐 사용한 다익스트라 표준)
- 공간: O(N + M)
구현 팁과 개선 포인트
- 함수명이 BFS()로 되어 있지만, 실제로는 다익스트라이므로 함수명을 Dijkstra()로 바꾸면 가독성이 좋아진다.
- 우선순위 큐에서 꺼낸 경로가 **구식(오래된)**일 수 있으므로 아래 한 줄을 넣으면 성능/안정성이 올라간다.
- if (value != dist[to]) continue; // 최단거리로 갱신된 최신 상태만 진행
- INF는 상수로 두는 것을 권장:
- const int INF = 1e9; vector<int> dist(N + 1, INF);
- 이 문제는 원 그래프에서 1번이 모든 노드에 도달 가능하다는 전제가 사실상 깔려 있다.
만약 일부 노드가 도달 불가능하다면 parent[v] == -1이 남을 수 있으므로, 실전 코드라면 이 경우를 체크해 별도 처리(예: 도달 가능한 노드만 출력)하는 방어 로직을 둘 수 있다.
예시 입력의 동작 직관
- 1에서 2,3,4로의 최단거리를 다익스트라로 구한다.
- 각 노드의 최단경로 직전 정점으로 구성된 간선 집합이 출력 예시처럼 나온다.
- 출력 간선 수는 항상 N-1이므로 조건 1 충족, 다익스트라의 최단거리 보존으로 조건 2 충족.
[소스 코드]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int value;
int to;
};
int N, M;
vector<vector<Node>> arr;
void Input() {
cin >> N >> M;
arr.resize(N + 1);
for (int i = 0; i < M; i++) {
int start, end, value;
cin >> start >> end >> value;
arr[start].push_back({value,end});
arr[end].push_back({ value,start });
}
}
struct cmp {
bool operator()(Node a, Node b) {
return a.value > b.value;
}
};
void BFS() {
priority_queue<Node, vector<Node>, cmp> pq;
pq.push({ 0,1 });
vector<int> dist(N + 1, 987654321);
vector<int> parent(N + 1, -1);
dist[1] = 0;
while (!pq.empty()) {
int value = pq.top().value;
int to = pq.top().to;
pq.pop();
for (Node node : arr[to]) {
int nextNode = node.to;
int nextValue = node.value + value;
if (nextValue < dist[nextNode]) {
dist[nextNode] = nextValue;
pq.push({ nextValue, nextNode });
parent[nextNode] = to;
}
}
}
cout << N - 1 << "\n";
for (int v = 2; v <= N; v++) {
cout << parent[v] << " " << v << "\n";
}
}
void Game_Start() {
BFS();
}
int main(void) {
Input();
Game_Start();
}