오늘의 알고리즘 -boj-9372

문제

상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.

하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.

이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.

상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

풀이

최소신장트리 문제라고 해서 보자마자 프림알고리즘으로 어떻게 풀지만 생각했는데(심지어 무지성으로 거의 작성까지 했었다!)문제를 자세히 보니까 간선의 갯수를 구하는 문제였다.

모든 국가를 방문할 때 비행기의 종류가 최소가 된다.
-> 최소한의 길을 이용하여 모든 정점들에 이동이 가능하도록 만들어진 트리 -> 신장트리

신장트리의 간선의 갯수 = 정점의갯수 -1

따라서 아래와 같은 코드가 나오게 된다.

from collections import deque
import sys
input = sys.stdin.readline

T = int(input().rstrip())

for _ in range(T):
    N , M = map(int, input().rstrip().split())
    
    for _ in range(M):
        a, b = map(int, input().rstrip().split())
        
    print(N-1)