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

문제

 

풀이

문제에서 주어진 정보를 잘 활용해야 한다.

주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

 

연결 그래프가 무엇인지 그림을 보면 쉽게 이해 가능하다.

 

따라서 아무 노드나 선택해도 그 노드에서 모든 노드로 갈 수 있음을 의미한다. (아래 그림 참고)

 

위 연결 그래프의 어떤 노드를 선택하든지 간에, 모든 노드로 갈 수 있음

 

또한 연결 그래프를 유지하기 위한 간선의 최소 개수는 (노드의 수 - 1)이다.

 

이를 신장 트리라 한다.

https://terms.naver.com/entry.naver?docId=837730&cid=42344&categoryId=42344 

신장 트리

 

즉, 비행기의 종류 = 간선 수

여행 갈 나라의 수 = 노드의 수

 

간선의 최소 수 = 노드의 수 - 1

코드

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    for _ in range(m):
        input() # 무조건 연결그래프이므로 입력 값을 무시한다.
    print(n - 1)

 

마무리

기본 지식을 묻는 문제, 처음 접하는 문제라 꽤 까다로웠다.