백준_python 9372번 상근이의 여행 (그래프, 트리)

<문제 링크>

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

'

 

<정답 코드>

 sol ) DFS로 국가(노드) 탐색하여 비행 횟수 구하기

import sys
input = sys.stdin.readline
 
def dfs(node, cnt):
    visited[node] = True
    for n in tree[node]:
        if not visited[n]:
            cnt = dfs(n, cnt+1)
    return cnt
 
t = int(input())
 
for _ in range(t):
    n, m = map(int, input().split())
    tree = [[] for _ in range(n+1)]
    visited = [False] * (n+1)
 
    for _ in range(m):
        u, v = map(int, input().split())
        tree[u].append(v)
        tree[v].append(u)
 
    visited[1] = True
 
    print(dfs(1,0))

 

DFS로 풀 수 있는 쉬운 문제였다.

그래프(트리) 배열로 구현