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

본문 링크

import sys
input=sys.stdin.readline



def DFS(start,Tree,parents):
    global count
    for i in Tree[start]:
        if Parents[i]==0:
            Parents[i]=start
            count+=1
            DFS(i,Tree,parents)


for i in range(int(input())):
    N,M=map(int,input().split())
    Tree=[ [] for _ in range(N+1)]
    Parents=[0]*(N+1)
    for j in range(M):
        a,b=map(int,input().split())
        Tree[a].append(b)
        Tree[b].append(a)

    count=0
    DFS(1,Tree,Parents)

    print(count-1)

📌 어떻게 접근할 것인가?

기본적인 트리 문제이다.
다만 문제에서는 가장 적은 비행기를 타고 모든 국가를 여행하는 것이다.
이때 한번 탄 비행기는 여러번 탈 수 있기 때문에
트리를 그저 한번 순회 해준후에 트리의 크기를 구해주면된다.

트리 순회를 하기 위해서 $DFS$ 알고리즘을 사용하였다.