백준 2211. 네트워크 복구

https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

 

문제에서 두개의 조건이 주어진다.

1. 최소 개수의 회선을 복구시켜야하고, 모든 노드들이 연결되어 있어야한다.

2. 슈퍼컴퓨터인 1번 노드에서 다른 모든 노드들이 최단거리로 연결되어야 한다.

 

그런데 1번 조건은 2번 조건을 충족시키면 저절로 충족된다. 

1번 노드에서 다른 모든 노드들이 최단거리로 연결되려면 당연히 모든 노드들은 서로 연결되어 있을 것이고, 최단거리로 연결되어 있기 때문에 갯수도 최소 갯수일 것 이다.

 

 

그럼 2번 조건을 충족시키면 되는데 그냥 조건만 봐도 다익스트라 알고리즘인것을 알 수 있다. 

문제는 다익스트라 알고리즘은 하나의 노드에서 다른 모든 노드들의 거리를 저장한다는 것이다.

그런데 이 문제는 거리가 아닌 간선을 출력해야 한다. 

 

간선 기억도 다익스트라에서 조금만 추가하면 가능하다.

int e[1001] 배열에 연결된 노드를 저장하도록 하면 된다.

즉 e[3] = 2 라면 3번 노드와 2번 노드가 연결되어 있다는 뜻이다. 

 

다익스트라 알고리즘에서 nextDistance가 해당 노드에 저장되어 있는 거리보다 짧다면 갱신하게 되는데, 이때 e[i] 즉 연결된 노드도 갱신하면 된다.

 

다익스트라 알고리즘 종료 후 e[i] > 0 인 노드들이 연결된 두 노드이므로 출력해주면 된다.