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

이번 문제는 풀이보다는 간단한 생각으로 바로 해결하였다. 처음에는 시작하는 시작점도 주지 않아서 어떻게 접근해야 할지 난감했지만, 문제에서 비행 스케줄이 항상 연결 그래프라는 부분을 보고 생각을 해냈다.

연결 그래프에서 모든 지역을 최소한의 비행으로 방문하기 위해서는 갔던 곳을 다시 가면 안된다. 즉 끝에서 끝까지 되돌아가지 않고 쭉 가야한다. 그러기 위해서는 단순하게 생각하면 n-1번의 비행을 최소한으로 해야 한다. 그래서 n-1을 출력하도록 하였더니 정답 처리 되었다.

이상해서 찾아보니 n-1을 출력하도록 하는 것이 출제 의도가 맞다고 한다..!!

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n, m=map(int, input().split())
    for _ in range(m):
        a, b=map(int, input().split())
    print(n-1)