[파이썬, Python] 백준 9372: 상근이의 여행

문제

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(idx, cnt):
    visited[idx] = 1
    
    for i in graph[idx]:
        if visited[i] == 0:
            cnt = dfs(i, cnt+1)
    
    return cnt

t = int(input())

for i in range(t):
    n, m = map(int, input().split())
    graph = [[] for i in range(n+1)]
    visited = [0] * (n+1)
    
    for i in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    print(dfs(1,0))

설명

DFS로 풀이했다.

방문하지 않은 모든 국가를 방문해야 하므로 dfs를 사용해서
방문하지 않은 국가를 만날 경우 방문을 하는 것으로 했다.

그런데 풀다 보니 모든 국가를 방문해야 하고,
모든 국가는 연결되어 있으므로
그냥 n-1개의 비행기를 타면 된다는 간단한 문제였다.