[백준 9372번] 상근이의 여행 (C++)

문제링크 : https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N, M;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    while(T--)
    {
        cin >> N >> M;
        for(int i=0; i<M; i++)
        {
            int a, b;
            cin >> a >> b;
        }
        cout << N-1 << "\n"; //ST 간선의 수
    }  
}

알고나면 상당히 허무한 문제이다.

문제에서 모든 국가들을 여행할 때 가장 적은 종류의 비행기를 구하도록하였다.

그리고 주어지는 비행 수케줄은 항상 연결 그래프를 이룬다고 명시되어있다.

 

결국 어느 노드를 고르든 몇 번의 이동을 거쳐서 다른 노드로의 이동이 가능하다.

이러한 형태의 최소 이동 횟수는 일직선과 같이 한번에 쭉 이동이 가능한 N-1개이다.

 

문제에서 모든 국가들이 정점의 수이고, 비행기의 종류가 간선이다.

따라서 a, b의 내용과는 관계없이 가장 적은 종류의 비행기를 나타내는 가장 적은 간선의 수는 항상 N-1개가 된다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

그래프 내의 모든 정점을 연결하고(항상 연결 그래프),

간선의 수가 가장 적은(가장 적은 종류의 비행기) 최소 연결 부분 그래프를 찾으므로 스패닝 트리 문제이다.

스패닝 트리의 간선의 수는 N-1이므로 마찬가지로 답은 N-1개를 출력해주면 된다.