문제
상근이는 겨울방학을 맞아 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
2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5예제 출력 1
2
4문제이해
문제는 상근이가 여러 국가를 여행할 때, 가장 적은 종류의 비행기를 타고 모든 국가를 여행할 수 있도록 하는 것
문제 분석
입력으로 주어지는 국가와 비행기 스케줄은 항상 연결 그래프를 이룹니다.
이말은 즉슨 그래프 이론의 MST(최소신장트리) 문제로 변환할 수 있다.
MST ?
- 스패닝 트리(Spanning Tree): 주어진 그래프의 모든 노드를 포함하면서, 그래프의 일부 간선들만 이용해 만든 트리, 원래 그래프의 모든 노드를 포함하지만, 모든 간선을 포함하지는 않음
- 최소 신장 트리(MST, Minimum Spanning Tree): 여러 개의 스패닝 트리 중에서 간선들의 가중치 합이 가장 작은 트리
각 국가를 노드로, 비행기를 간선으로 생각할 수 있다
모든 국가를 여행하려면 최소한의 비행기를 타야 하므로, 이는 그래프에서 모든 노드를 포함하는 최소 신장 트리를 찾는 문제
연결된 그래프에서 최소 신장 트리를 찾기 위해 필요한 간선의 수는 항상 노드의 수 - 1
자료구조 선택
이 문제는 MST 문제로 기본적으로는 그래프를 표현하기 위한 자료구조가 필요
국가와 비행기를 표현하기 위해 리스트나 집합을 사용할 수 있지만, 사실 MST의 성질을 이용하면 간선을 실제로 저장할 필요는 없다.
최소 신장 트리를 찾는 알고리즘(크루스칼, 프림 등)을 사용할 수 있지만, 연결된 그래프에서 항상 N-1 간선이 필요하다는 사실을 이용하여 간단히 해결할 수 있음
알고리즘 설계
문제를 단순화하면, 각 테스트 케이스마다 N-1을 출력하면 된다. 이는 주어진 연결 그래프에서 MST를 만들기 위해 필요한 최소 간선의 수가 N-1이기 때문
정답코드
#9372
#최소 신장 트리
import sys
T = int(sys.stdin.readline())
for i in range(T):
N, M = map(int, sys.stdin.readline().split())
for j in range(M):
u, v = map(int, sys.stdin.readline().split())
print(N - 1)