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

문제링크

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

풀이방법

해당 문제는 신장 트리 알고리즘의 원리를 이용해서 바로 답을 구할 수 있다 신장 트리의 원리는 다음과 같다.

신장 트리란?
신장 트리(Spanning Tree)는 그래프의 최소 연결 부분 그래프 이다.
최소 연결 = 간선의 수가 가장 적다.
n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.
즉, 그래프에서 일부 간선을 선택해서 만든 트리

따라서 위 이론을 문제에 적용하면 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수는 즉, N개의 노드(비행기가) 있을 때 가능한 최소의 간선 수=N-1이 된다. 정답 코드는 아래와 같다.

코드

#include <bits/stdc++.h>
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        int a, b;
        while (m--) cin >> a >> b;
        cout << (n - 1) << '\n';
    }
}

/*
MST(신장 트리) 문제라는 것을 파악했다면 (정점의 수)-1개의 간선이 필요하기 때문에
주어지는 입력을 받고 간선의 수를 출력하면 된다.
*/