[백준 9372] 상근이의 여행 (C++)

문제 링크: www.acmicpc.net/problem/9372

9372번: 상근이의 여행

1. 주의할 점

- DFS, BFS, MST, 한줄 모두 가능

- 허무주의

 

2. 구현

[BFS]

- 시작점을 1로 잡고(아무점이나 상관없다) Queue에 넣고 BFS를 수행한다. 방문하지 않은 Node가 있으면 Result++하고 Queue에 넣는다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[1001];
bool check[1001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test;
	cin >> test;
	for (int t = 0; t < test; t++) {
		int node, edge, a, b;
		cin >> node>> edge;
		for (int i = 1; i <= node; i++) {
			v[i].clear();
			check[i] = false;
		}
		for (int i = 0; i < edge; i++) {
			cin >> a >> b;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		int result = 0;
		queue<int> q;
		q.push(1);
		check[1] = true;
		while (!q.empty()) {
			int cidx = q.front();
			q.pop();
			for (int i = 0; i < v[cidx].size(); i++) {
				int next = v[cidx][i];
				if (!check[next]) {
					check[next] = true;
					result++;
					q.push(next);
				}
			}
		}
		cout << result << '\n';
	}
	return 0;
}

 

[한줄]

- 문제를 잘못읽었나 싶었다. 하지만 아니였다

- 힌트)

• 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다
• 가중치가 존재 X

- 모든 Node가 연결된다 + 가중치가 없다 -> MST다 -> MST의 조건은 간선의 개수가 Node-1개다

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test;
	cin >> test;
	for (int t = 0; t < test; t++) {
		int node, edge, a, b;
		cin >> node>> edge;
		for (int i = 0; i < edge; i++) 
			cin >> a >> b;
		cout << node-1 << '\n';
	}
	return 0;
}

 

 

※ 문제 출제자의 의도

: Node-1을 출력하여 O(1)의 시간복잡도를 가진다