백준 9372 c++

 

 

 

도저히 이해를 못하겠어서 다음날 정답지를 봤다

 

 

 

 

 

 

 

처음에는 BFS(Breadth First Search) 알고리즘을 적용하려고 했지만 그럴 필요가 없다는 것을 깨달았습니다.

최소 스패닝 트리(Minimum Spanning Tree)는 N-1개의 간선으로 이루어져있기 때문에 결국 N-1 개의 간선 즉, N-1 종류의 비행기를 타야지 모든 도시를 방문할 수 있다는 것을 알 수 있습니다.

 

라는데 하 잘모르겠다.

 

 

 

 

친구한테 물어봤는데

 

3 3 ; 나라 3개, 비행기 3개

1 2 ; 1번 비행기: 1<->2 나라로 이동

2 3 ; 2번 비행기: 2<->3 나라로 이동

1 3 ; 3번 비행기: 1<->3 나라로 이동

 

 

5 4 ; 국가 5개 4비행

2 1 ; 2<->1

2 3 ; 2<->3

4 3 ; 4<->3

4 5 ; 4<->5

 

 

이해를 완료했다. ㅋ

 

 

테스트 케이스는 2개이고  2개의 케이스를 입력했고,

그다음 국가n과 비행기 m 을 입력후

m개의 선을 긋는거다.

 

 

적고보니 문제에서 요구한대로 똑같이 적었네?

하 이해력이 왤케 딸리는거같지 ...

 

일단 이해완료했으니 코드를보자

 

#include <iostream>

 

using namespace std;

 

int main() {

int T;

cin >> T;

 

while (T--) {

int N, M;

cin >> N >> M;

 

int a, b;

while (M--) {

cin >> a >> b;

}

 

cout << N - 1 << endl;

}

 

}

 

 

최소로 이으면 애벌레처럼 한줄이니 N-1 이다