[백준] 실버2 : (11725) 트리의 부모 찾기

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

 

각 정점의 부모를 찾는 문제이다.

 

노드들의 부모-자식 관계를 알 수 없으니, 그래프의 형태로 노드의 연결을 저장한다.

 

트리의 루트는 항상 1이다.

따라서 1의 자식 노드는 항상 부모 노드가 1이다.

1의 자식 노드를 n이라고 한다면, n의 자식 노드는 항상 부모 노드가 n이다.

 

이 과정은 트리의 루트부터 높이가 높아지며 BFS로 검사하는 것과 같다.

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

int N;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	vector<int> Node(N + 1);			// 1...N 노드의 부모 노드
	vector<bool> Visit(N + 1);			// 방문(부모 찾기)한 노드
	vector<vector<int>> Tree(N + 1);	// 각 노드와 연결된 노드

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

		Tree[a].push_back(b);
		Tree[b].push_back(a);
	}

	// 트리의 루트인 1부터 시작
	queue<int> q;
	q.push(1);
	Visit[1] = true;

	while (!q.empty())
	{
		int n = q.front();
		q.pop();

		// 현재 검사중인 노드의 자식 노드를 검사
		for (int k = 0; k < Tree[n].size(); ++k)
		{
			int nn = Tree[n][k];
			if (Visit[nn]) continue;

			Visit[nn] = true;
			Node[nn] = n; // 발견한 자식 노드의 부모 노드는 현재 검사중인 노드이다.
			q.push(nn);
		}
	}

	for (int i = 2; i <= N; ++i)
		cout << Node[i] << "\n";
}