[백준] 9372 상근이의 여행(Python)

백준 - 9372 상근이의 여행

풀이

처음에는 모든 점에서 dfs를 한 후 깊이를 비교해서 답을 도출하려고 했다.
그런데 문제에 엄청난 힌트가 있었다................

그래프가 주어지고 모든 국가(정점)를 방문할 수 있는 가장 적은 비행기(간선)의 종류의 수를 구하라고 했다.
그리고 그래프는 연결그래프라고 했다...

결국 신장 트리 -> 간선의 개수를 구하는 문제이므로 N(정점의 개수)-1이 답....
(황당)

처음에는 국가 방문 경로에 따른 비행기를 타는 횟수라고 생각했다.
그래서 dfs를 하려고 한 거였다...
40분을 이렇게 저렇게 하다가 나중에서야 알았따....

왠지 모르게 킹받는 문제였다 ㅎ

앞으로 정신차리고 글을 잘 읽도록 하자

코드

from sys import stdin

for i in range(int(input())):
    n, m = map(int, stdin.readline().split())
    for j in range(m):
        a, b = map(int, stdin.readline().split())
    print(n - 1)