백준 9372 상근이의 여행 - C++

얼핏 보면 순회문제처럼 보인다.

하지만 이 문제에는 치명적인 함정이 있다.

그것은 바로 "비행기의 종류"를 세는 문제라는 것!

 

무슨 뜻이냐면,

A 나라에서 B 나라로 한 번에 날아간다고 가정하자.

그러면 A <-> B 를 아무리 왕복해도

종류는 1가지 뿐이다.

 

또한 문제에서 항상 연결 그래프를 이루고 있다는 것이

보장되어 있기 때문에 우리는 

비행기를 몇 번 타느냐가 아니라

몇 종류를 타느냐에만 집중하면 된다.

 

그렇다면 몇 종류를 타야할까?

만약 당신이 중국 일본 한국 대만을 가야하고

모든 노선이 항상 존재한다고 한다면

비행기를 몇 종류 타야할까?

아무리 적어도, 아무리 많아도

3번은 타야 모든 나라를 갈 수 있을 것이다.

그렇지 않은가?

 

따라서 이 문제의 정답은 

딱히 입력을 받지 않더라도 

N개의 국가일 때 N-1개의 종류임이 자명하다.

 

고로 N-1 을 출력하면 정답.

 

만약 순회로 풀어도

조금 시간이 오래걸릴 뿐 통과는 가능하다.

#include <stdio.h>
#include <string.h>
using namespace std;
int Airplane[1001][1001];


int main() {
	int T;
	scanf("%d", &T);
	for (int loop = 0; loop < T; loop++) {
		memset(Airplane, 0, sizeof(Airplane));
		int N, M;
		scanf("%d %d", &N, &M);
		for (int i = 0; i < M; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			Airplane[a][b] = 1;
			Airplane[b][a] = 1;
		}
		printf("%d\n", N - 1);
	}




}