[BOJ] 9372 상근이의 여행 C++

개요

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

9372번: 상근이의 여행

실버4 난이도 문제다.

풀이

처음 문제를 봤을 때는 그래프의 탐색으로 접근하려고 했다.

근데 그렇다고 하기엔 난이도가 낮았다. (꼼수 , , )

 

처음에는 비행기를 탑승한 횟수인 줄 알았는데, 다시 보니 탑승한 비행기의 종류를 구하는 문제였다.

어차피 N개의 노드를 방문하려면 무조건 N-1개의 간선을 지나야 한다.

 

그래서 N-1을 출력해 줬더니 해결됐다.

 

이런 문제 너무 재밌다 , , !

코드

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int T, N, M;
	int a, b;

	cin >> T;

	while(T--)
	{
		cin >> N >> M;

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