백준9372 - 상근이의 여행

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

9372번: 상근이의 여행

풀고 나니까 되게 허탈한 문제였다. 나는 BFS로 구현해서 풀었다. 현재 노드에서 다른 노드로 왕복 가능한 비행기들이 주어지고 출발점부터 모든 노드까지 이동 가능한 경로를 세어주면 된다. 방문한 곳은 다시 방문하지 않는다. 그러면 자연스럽게 중복된 경로는 세지 않게 된다. 그런데 이렇게 풀 필요가 없이 최소 스패닝 트리를 구하면 되고 모든 경로를 한번씩 모두 거쳐만 가면 되니까 주어진 나라의 갯수에서 -1만 하면 된다. 허탈했다.

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

int T, N, M;
int a, b;
int cnt = 0;
int x;
bool visit[1001];
vector<int> v[1001];
queue<int> q;

//bfs로 구현, 방문한 곳은 재방문하지 않는다.
void bfs(int x) {
	q.push(x);
	visit[x] = true;
	while (!q.empty()) {
		x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size(); i++) { //현재 노드에서 도달 가능한 노드르 모두 탐색한다.
			if (!visit[v[x][i]]) {
				visit[v[x][i]] = true;
				q.push(v[x][i]);
				cnt++;
			}
		}
	}
}

int main() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N >> M;

		//초기화
		cnt = 0;
		for (int j = 0; j < 1001; j++) {
			v[j].clear();
		}
		memset(visit, false, sizeof(visit));

		for (int j = 0; j < M; j++) {
			cin >> a >> b;
			if (j == 0) {
				x = a;
			}
			v[a].push_back(b); //a -> b
			v[b].push_back(a); //b -> a
		}
		bfs(x);
		cout << cnt << '\n';
	}
}