백준 9372번 상근이의 여행

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

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

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

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N, M;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int T;

        cin >> T;

 

        while (T--)

        {

                 cin >> N >> M;

 

                 for (int i = 0; i < M; i++)

                 {

                         int node1, node2;

                         cin >> node1 >> node2;

                 }

                 //MST는 N-1개의 간선으로 이루어져있다

                 cout << N - 1 << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~