[백준 9372 파이썬] 상근이의 여행 (실버 4, 신장 트리)

알고리즘 유형 : 신장 트리
풀이 참고 없이 스스로 풀었나요? : 학습

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
def DFS(node, cnt):
    visited[node] = 1
    
    for adj_node in graph[node]:
        if visited[adj_node] == 0:
            cnt = DFS(adj_node, cnt+1)
    
    return cnt

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    visited = [0]*(N+1)
    
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    print(DFS(1, 0))
    

풀이 요약

1. 임의의 연결 그래프에 대해, 신장 트리는 사이클이 없고 연결 그래프의 모든 노드가 연결되어 있는 부분 그래프이다.

   따라서, DFS나 BFS로 모든 노드를 탐색해주면 그 경로 자체가 신장 트리가 되고, 새로운 노드를 탐색할 때마다 cnt를 1씩 더해주고, 탐색의 마지막에 다다르면 이 cnt를 리턴해주면 그게 답이다.

   사실 연결 그래프이므로, 답은 그냥 항상 N-1이긴 하다.

배운 점, 어려웠던 점

• 신장 트리의 개념을 익혔다.