[BOJ] 2211번 네트워크 복구 (C++)

문제 (https://www.acmicpc.net/problem/2211)

2211번: 네트워크 복구

처음엔 MST를 사용해야하나? 라는 생각이 들었지만 다익스트라로 만들어진 MST와 MST는 서로 다르다는 반례를 보고 다익스트라로 문제를 해결했다.

 

11779 최소비용 구하기 2 문제에서 사용했던 방식과 유사하다. route라는 배열을 생성하여 배열의 해당 인덱스에 도달하기 위해서는 몇 번에서 와야 하는지를 기록한다.

route[a] = b는 "a번에 최소로 도달하기 위해서는 b번에서 와야 한다"라는 의미

 

네트워크를 복구하기 위해서는 무조건 n-1개의 회선을 복구하면 되므로 첫 번째 출력 값은 n-1이다.

복구할 회선들을 출력하는 경우 2부터 n까지 반복하며 route 배열의 인덱스와 값을 같이 출력해주었다. (즉, route[i], i = 출발 번호, 도착 번호)

---

[소스코드]

---

2022-01-10

Gold 2

- 그래프 이론

- 다익스트라