난이도 : 실버 4
유형 : 최소 신장 트리
https://www.acmicpc.net/problem/9372
문제요약
상근이는 N개국을 여행하기로 마음먹었다.
최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.
상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.
상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도 (심지어 이미 방문한 국가라도) 된다.
입력
첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,
각 테스트 케이스마다 다음과 같은 정보가 주어진다.
첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b)
주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.
출력
테스트 케이스마다 한 줄을 출력한다.
상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.
해결 아이디어
상근이가 가장 적은 종류의 비행기로 모든 국가를 여행하고 싶다고 한다.
예제 1 - 첫번째 테스트케이스를 보면
3 3
1 2
2 3
1 3
를 입력 받는다.
이는 3개의 국가를 여행할건데 ,
비행기의 노선 종류가 3개 (1-2, 2-3, 1,3)가 있다는 뜻이다.
모든 국가를 여행해야 하니 이때는 1-2, 2-3 비행기노선만 이용하여도 다 가능하니 최소 비행기의 개수는 2이다.
예제 2 - 두번째 테스트케이스를 보면
5 4
2 1
2 3
4 3
4 5
를 입력 받는다.
이는 5개의 국가를 여행할건데
비행기 노선 종류가 4개 (2-1,2-3,4-3,4-5) 가 있다는 뜻이다.
1,2,3,4,5 국가 다 여행할ㄷ 때 필요한 최소비행기의 수는
(2-1,2-3,4-3,4-5) 다 필요하다.
=> 4 출력
그렇다면 어떻게 풀까?
문제의 본질은 모든 국가를 이동할 수 있도록 하되, 비행기 노선(간선)을 최소한으로 사용하는 것이다.
이것은 최소 신장 트리(MST: Minimum Spanning Tree) 의 정의와 완전히 동일하다.
최소 신장 트리란?
- 모든 정점을 연결하면서
- 간선의 수가 최소가 되는 트리 구조
간선의 수 = 정점의 수 - 1
- 입력으로 주어지는 그래프는 항상 연결 그래프라고 했기 때문에
모든 국가가 반드시 한 트리로 연결된다는 보장이 있다. - 따라서 비용이 아니라 간선 수만 최소화하면 되므로
간선의 개수는 노드 -1 이기에, 그냥N - 1출력하면 끝난다
해답 및 풀이
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
for _ in range(M):
input() # 비행기 노선 정보는 필요 없음
print(N - 1) # 최소 간선의 개수 = 국가 수 - 1