[백준/C++] 11725번 트리의 부모찾기 / BFS/ 코딩테스

백준 11725번 트리의 부모 찾기  

 

---

11725번 풀이

이 문제도 일반적인 BFS 형식의 확정 문제이다. 

결국에는 '각 노드의 부모 노드가 무엇이냐' 를 찾는 문제인데, 트리 구조를 바탕으로 하지만 트리의 층 순서대로 주는 것이 아닌 뒤죽박죽 형식으로 주기 때문에 결국에는 한번에 다 받은 다음에 BFS 구조로 찾는 방법으로 다가갔다. 

 

for (int i = 0; i < n - 1; i++) {
	int a, b;
	cin >> a >> b;

	if (a == 1) {
		parent[b] = 1;
		Q.push(b);
		vist[b] = 1;
	}
	else if (b == 1) {
		parent[a] = 1;
		Q.push(a);
		vist[a] = 1;
	}
	vec[a].push_back(b);
	vec[b].push_back(a);
}

1층의 노드는 무조건 1이라는 조건이 있었기 때문에, 그래도 중간에 각 연결된 노드들을 입력 받는 과정에서 부모 노드를 갖는 아이들를 판별해 Q에 넣어줄 수 있었다.

 

위 코드 처럼 입력되는 a, b 중 1인 것을 확인한다. 만약, a가 1이라면 b의 parent 노드는 확정적으로 a이다. 그리고 이 b를 q에 넣어주었다. 이유는 트리 구조이기 때문에 '1 -> b -> b의 자식' 노드 순인 것은 확정적이기 때문이다. 

 

그리고 Q에 들어가서는 그 자식의 자식 노드들을 계속 쌓아주고, parent 노드를 입력해주면 끝!

 

---

백준 11725번 트리의 부모찾기 C++ 전체 코드 

 

#include <iostream>
#include <queue>
#include<vector>
using namespace std;

bool vist[100001];
int parent[100001] = {};
queue<int> Q;
vector<int> vec[100001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	vist[1] = 1;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;

		if (a == 1) {
			parent[b] = 1;
			Q.push(b);
			vist[b] = 1;
		}
		else if (b == 1) {
			parent[a] = 1;
			Q.push(a);
			vist[a] = 1;
		}
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			if (vist[vec[cur][i]] == 1) continue;
			parent[vec[cur][i]] = cur;
			Q.push(vec[cur][i]);
			vist[vec[cur][i]] = 1;
		}
	}
	for (int i = 2; i < n + 1; i++) {
		cout << parent[i] << '\n';
	}

	return 0;
}