문제 (https://www.acmicpc.net/problem/2211)
2211번: 네트워크 복구
첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다
www.acmicpc.net
처음엔 MST를 사용해야하나? 라는 생각이 들었지만 다익스트라로 만들어진 MST와 MST는 서로 다르다는 반례를 보고 다익스트라로 문제를 해결했다.
11779 최소비용 구하기 2 문제에서 사용했던 방식과 유사하다. route라는 배열을 생성하여 배열의 해당 인덱스에 도달하기 위해서는 몇 번에서 와야 하는지를 기록한다.
route[a] = b는 "a번에 최소로 도달하기 위해서는 b번에서 와야 한다"라는 의미
네트워크를 복구하기 위해서는 무조건 n-1개의 회선을 복구하면 되므로 첫 번째 출력 값은 n-1이다.
복구할 회선들을 출력하는 경우 2부터 n까지 반복하며 route 배열의 인덱스와 값을 같이 출력해주었다. (즉, route[i], i = 출발 번호, 도착 번호)
[소스코드]
'ALGORITHM > BOJ' 카테고리의 다른 글
| [BOJ] 3078번 좋은 친구 (C++) (0) | 2022.01.19 |
|---|---|
| [BOJ] 2096번 내려가기 (C++) (0) | 2022.01.19 |
| [BOJ] 13549번 숨바꼭질 3 (C++) (0) | 2022.01.17 |
| [BOJ] 1238번 파티 (C++) (0) | 2022.01.17 |
| [BOJ] 2887번 행성 터널 (C++) (0) | 2022.01.05 |