9372.상근이의 여행

이번에 풀어볼 문제는 백준 9372의 상근이의 여행이라는 문제이다.

9372번: 상근이의 여행

Spanning Tree에 대해서 공부할 수 있는 문제이며 최소 신장 트리(MInimum Spanning Tree)까지 공부할 수 있었다.

Spanning Tree : 방향이 없는 그래프에서 모든 정점들을 연결함과 동시에 순환경로가 없는 형태를 의미한다.

=> 만약 이와 같은 상황에서 가중치가 포함되고 최소 가중치만을 이용하여 연결하는 경우를 최소 신장 트리라고 한다.

이 문제를 잘 읽어보면 일단 최소 신장 트리 문제는 아니다. 간선에 대한 가중치에 대한 언급이 없기 때문이다.

 

 

 

---

 

* 참 고

최소 신장 트리를 구하는 알고리즘에는 대표적으로 크루스칼 알고리즘, 프림 알고리즘이 있다.

1. 크루스칼 알고리즘 (간선 기반) O(elog₂e)

탐욕적인 방법을 이용한 것으로 특징으로는 간선을 오름차순으로 정렬한 뒤 최소 간선 부터 선택한다.

주의할 점은 사이클이 형성되면 안된다.

 

2. 프림 알고리즘 ( 정점 기반 ) O(n^2)

시작 정점에서 시작하여 인접간 정점과의 간선의 가중치가 적은 간선부터 선택하여 진행한다.

 

---

 

또한 해당 문제 조건에서 주어진 비행 스케줄은 항상 연결 그래프라고 했다.

=> 즉, 모든 정점들이 연결되어있다고 했다.

=> 모두 연결된 상태에서 최소의 비행기 종류를 물어봤기 때문에 신장 트리라고 생각하면 된다.

=> 그러므로 정점 - 1 이 정답이 된다

한마디로 문제를 풀 필요가 없이 그냥 정점 - 1 이 정답이다...

그냥 입력받은 받되 정점 개수 - 1 을 출력해주면 된다!

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
 
using namespace std;
 
int T, N, M;
int main() {
    freopen("9372.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        cin >> N >> M;
        for (int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
 
        }
        cout << N-1 << endl;
    }
    return 0;
}