[BOJ][Python]9372번 풀이

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

9372번: 상근이의 여행

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n,m = map(int, input().split())
    v = [list(map(int, input().split())) for _ in range(m)]
    print(n-1)

당연하다면 당연한 것이고 꼼수라면 꼼수가 있는 문제입니다. 모든 노드가 연결되어있을 때 모조리 방문하기 위해서 거쳐야 하는 간선의 갯수는 노드 갯수 - 1 입니다. 따라서 n-1을 해주면 답을 구할 수 있는 조금 허무한 문제가 아닌가 싶네요. dfs로 푸신다고 하면 2차원 리스트를 만들어서 거쳤던 간선은 방문처리를 해뒀다가 cnt를 안올리도록 하면 될 것 같아요.