[백준 2211 C++] 네트워크 복구

오늘은 백준 2211번 네트워크 복구 문제에 대해 다뤄볼 예정이다.

네트워크 복구 문제 링크 (백준 2211번 문제): https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

 

문제 설명 

백준 2211번 네트워크 복구 문제는 서로 다른 컴퓨터 간에 네트워크 연결이 되어있는데, 시작 위치(슈퍼 컴퓨터: 1)에서 각 노드에 최단 거리로 도달하도록 하는 간선(edge)의 vertex들을 출력하는 문제이다. 

 

아래와 같은 입력이 들어왔다고 가정한다면, 

4 5

1 2 1

1 4 4

1 3 2

4 2 2

4 3 3

최단 거리

위 그래프와 같이 최단 경로를 나타낼 수 있을 것이다. 

즉, 1 -> 2 로 가는 최단 거리는 1, 1 -> 4 로 가는 최단 거리는 3, 1 -> 3 로 가는 최단 거리는 2로

빨간 색 간선(Edge)를 거쳐서 최단거리를 구한다. 

이러한, 빨간 색 간선을 출력해주면 되는 것이다. 

 

문제 풀이

특정 시작 노드에서 각 특정 노드까지 최단 거리(Shortest Path)를 구하기 위해서는 다익스트라 알고리즘(Dijkstra Algorithm)을 사용해주면 된다. 

 

이 문제에서 주목할 부분은 시작 노드가 아닌 각 노드에 초점을 두는 것이다. 

만일, 시작 노드(슈퍼 컴퓨터: 1)에서 다른 노드까지 최단 거리를 구하는 과정에서, 새로 업데이트 되는 최단 거리가 등장할 경우, 해당 Path를 저장해주면 된다. 즉, 최단 거리(Shortest Path)로 가기 위한 새로운 Path가 열렸을 경우, 해당 Path를 저장해주고, 기존에 있던 Path가 존재한다면, 기존 Path를 삭제해주면 된다. 

 

이를 코드로 나타내면 아래와 같이 나타낼 수 있다.