[백준/Python] 9372번 상근이의 여행

문제

 

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

9372번: 상근이의 여행

 

 

 

---

Algorithm

모든 국가를 여행하기 위해 타야하는 비행기의 최소 갯수를 묻는 문제이다. 

비행기의 최소갯수를 구하려면 각 지역을 1번씩만 방문하는게 당연히 최소가 될것이므로 이미 방문한 노드면 방문하지 않는 dfs를 사용하면 좋을것 같았다.

재귀를 이용하여 dfs를 구현하였고, 재귀가 호출될때마다 노드를 옮긴것이고, 즉 비행기를 탔다는 소리이므로 ans변수를 이용해 재귀가 몇번 호출되어 모든 지역을 방문하였는지 리턴해주면 그것이 최솟값이 될것이다.

단방향이 아니고 쌍방향이므로 graph를 구성할때 2번 입력을 해준다.

---

 

 

Code

input = __import__('sys').stdin.readline
from collections import deque

def dfs(graph, v, visited,ans):	#dfs
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            ans = dfs(graph, i, visited,ans+1)
    return ans
    
t = int(input())
for l in range(t):
    n,m = map(int,input().split())
    graph = [[]for _ in range(n)]
    visited = [False]*n
    for _ in range(m):
        a,b = map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    print(dfs(graph,0,visited,0))