백준 11725 - 트리의 부모찾기

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

본 문제의 분류는 트리이지만 그래프에 대한 자료주고를 만들고 탐색할 수 있어야 해결이 가능하다.

연결된 두 노드간 부모 자식이 누구인지 정보가 주어지지 않기 때문이다. 따라서 최초 자료구조를 만들때에는 그래프 처럼 만들어야 한다.

루트 노드가 주어졌기 때문에 BFS 순회를 하면서 부모와 자식 관계를 업데이트 한 후 순서대로 출력하면 된다.

 

다만 주의해야할점은 cin , cout 으로입출력을 하면 성능상 시간 초과가 발생하니 scanf 와 printf 를 사용하여야 한다.

 

구현된 코드는 아래와 같다.

 

 

 

#include <iostream>
#include <vector>

#include <queue>

using namespace std;

int main()
{
	int nrNode;
	cin >> nrNode;

	vector<int> parent(nrNode + 1);
	vector<bool> visit(nrNode + 1, false);
	vector<vector<int>> gp(nrNode + 1);

	for (int i = 0; i < nrNode-1; i++)
	{
		int t1, t2;
		scanf("%d%d", &t1, &t2);
		gp[t1].push_back(t2);
		gp[t2].push_back(t1);
	}

	queue<int> q;
	q.push(1);

	while (!q.empty())
	{
		int c = q.front();
		q.pop();
		visit[c] = true;
		for (unsigned int i = 0; i < gp[c].size(); i++)
		{
			int &adj = gp[c][i];
			if (visit[adj] == false)
			{
				parent[adj] = c;
				q.push(adj);
			}
		}
	}
	for (int i = 2; i <= nrNode; i++)
	{
		printf("%d\n", parent[i]);
	}
}