[백준][BOJ2211] 네트워크 복구

Algorithm/Dijkstra

by bedamino 2021. 7. 21. 20:22

1. 문제 : https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다

www.acmicpc.net

2. 풀이 : Dijkstra

3. 설명

문제의 조건은 아래와 같다.

1. 모든 컴퓨터를 최소 개수의 회선으로 복구한다.

2. 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 시간이 최소가 되어야 한다.

모든 컴퓨터를 최소의 회선으로 복구하려면 (컴퓨터 수 - 1) 만큼의 회선이 필요하다.

슈퍼컴퓨터로부터 모든 컴퓨터를 최소의 시간으로 연결하면서 경로를 갱신하면 각 컴퓨터들에 연결된 회선 정보를 알 수 있다.

4. 코드

저작자표시 비영리 변경금지

날마다 새로운 코딩