[백준] 9372번 상근이의 여행 (feat. 그래프 이론, 최소 신장 트리)

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

 

문제 분석

• 첫 번째 단계(문제 요약 및 조건 파악)

- 문제 요약
N개의 국가를 여행하려고 함.
비행 스케줄이 주어졌을 때, 가장 적은 종류의 비행기를 탈 수 있도록 하는 프로그램을 작성할 것.
한 국가에서 다른 국가로 이동할 때, 다른 국가를 겨쳐 가도됨.

- 입력
첫 번째 줄에는 테스트 케이스의 수 T(T <= 100)
각 테스트케이스는
    - 첫 번째 줄에는 국가의 수 (2 <= N <= 1000)과 비행기의 종류(1 <= M <= 10000)가 주어짐
    - 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미(1 <= a, b <= n; a != b)
    - 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

- 출력
테스트 케이스마다 한 줄을 출력한다.
    - 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력

 

• 두 번째 단계(문제 핵심 파악)

i)
문제의 입력조건을 다시한번 살펴보면,
"주어지는 비행 스케줄은 항상 연결 그래프를 이룬다."라고 했다.
그렇다면, 모든 국가가 비행기로 연결되어 있음을 의미한다.

그렇다면, 최소 신장 트리의 간선의 갯수를 구하는 문제인데,
최소 신장 트리의 간선의 갯수는 노드의 갯수 -1 이다.

이문제에서 노드는 국가이므로,
국가의 갯수 - 1을 해주면 답으로 예상한다.

사실 처음에는, 모든 간선의 가중치를 1로 두고, 크루스칼 알고리즘을 적용해보려고 했다.
그런데, 문제 조건을 다시 생각해보니,
연결 그래프고, 최소 신장 트리의 간선의 갯수를 구하는 문제였고,

최소 신장 트리의 간선의 갯수는 연결 그래프의 노드의 갯수 - 1
빠르게 문제를 해결할 수 있었다.

 

코드 작성

 

'''
- 문제 요약
N개의 국가를 여행하려고 함.
비행 스케줄이 주어졌을 때, 가장 적은 종류의 비행기를 탈 수 있도록 하는 프로그램을 작성할 것.
한 국가에서 다른 국가로 이동할 때, 다른 국가를 겨쳐 가도됨.

- 입력
첫 번째 줄에는 테스트 케이스의 수 T(T <= 100)
각 테스트케이스는
    - 첫 번째 줄에는 국가의 수 (2 <= N <= 1000)과 비행기의 종류(1 <= M <= 10000)가 주어짐
    - 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미(1 <= a, b <= n; a != b)
    - 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

- 출력
테스트 케이스마다 한 줄을 출력한다.
    - 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력

i)
문제의 입력조건을 다시한번 살펴보면,
"주어지는 비행 스케줄은 항상 연결 그래프를 이룬다."라고 했다.
그렇다면, 모든 국가가 비행기로 연결되어 있음을 의미한다.

그렇다면, 최소 신장 트리의 간선의 갯수를 구하는 문제인데,
최소 신장 트리의 간선의 갯수는 노드의 갯수 -1 이다.

이문제에서 노드는 국가이므로,
국가의 갯수 - 1을 해주면 답으로 예상.

'''
import sys

# 테스트 케이스의 개수
t = int(sys.stdin.readline())

for i in range(t):
    # 국가의 수 n, 비행기의 종류 m
    n, m = map(int, sys.stdin.readline().strip().split())
    for j in range(1, m + 1):
        input() # 입력 무시
    print(n - 1)    # 최소 신장 트리의 간선의 갯수 =  노드의 개수 - 1

※ 이 문제는 최소 신장 트리의 간선의 갯수가 n - 1인 것을 이해하고 있으면 쉽게 풀이할 수 있는 문제다.

문제 의도 자체가 MST의 간선 갯수가 노드갯수가 n일 때, n-1 인것을 이해하고 있느냐 였던 문제!