[C/C++] 백준 9372번 - 상근이의 여행

 

 

<코드>

#include<iostream>
using namespace std;

int T, N, M, a, b;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> N >> M;
        for (int i = 0; i < M; i++)
            cin >> a >> b;
        cout << N - 1 << '\n';
    }

}

 

풀이 방법

문제에 가중치가 없기 때문에 노트에 끄적이다가 N개의 도시를 여행하려면 최소한 N-1번은 비행기를 타야 하므로 단순히 N-1이 답이 아닌가 해서 제출해보니 통과되었다.

MST알고리즘의 경우 간선의 개수는 항상 N-1이므로 N-1이 정답이다.

질문글을 읽어보니 N-1이 출제 의도였다고 한다...

 

www.acmicpc.net/problem/9372

9372번: 상근이의 여행