[C++] 백준 11725번 - 트리의 부모 찾기

트리를 활용한 문제이다. 

사실 트리 문제가 나오면 DFS를 활용하는 것이 정배라고는 하지만 이 문제는 단순히 BFS를 통해서 문제를 풀 수 있었다.

1번 Node는 고려하지 않으므로, 1번 Node에서 출반하여 BFS 탐색을 수행하면 문제가 풀린다.

문제는 항상 root node가 1이 아니기 때문에 입력에서 양방향 인접리스트로 받았는데,

이제 visited한 것을 잘 처리해주면 된다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pii pair<int, int>
using namespace std;

int n;
vector<int> tree[100001];
bool visited[100001];


int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	queue<int> q;
	vector<pii> v;
	q.push(1);
	visited[1] = true;

	while (!q.empty()) {
		auto cur = q.front(); q.pop();

		if (!tree[cur].empty()) {
			for (int i = 0; i < tree[cur].size(); i++) {
				if (!visited[tree[cur][i]]) {
					q.push(tree[cur][i]);
					v.push_back({ tree[cur][i], cur });
					visited[tree[cur][i]] = true;
				}
			}
		}
	}

	sort(v.begin(), v.end());

	for (auto& item : v) {
		cout << item.second << endl;
	}

	return 0;
}