[백준] 트리의 부모 찾기 (11725번)

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

7 1 6 6 3 3 5 4 1 2 4 4 7

예제 출력 1 복사

4 6 1 3 1 4

---

트리의 루트를 제외한 모든 노드의 부모 노드를 출력하는 문제이다.

문제를 제대로 안 읽고 풀어서 union과 find를 활용하는 disjoint set 문제인 줄 알았는데, 단순 트리의 부모만을 구하면 되는 bfs, dfs를 이용한 문제였다. bfs야 워낙 많이 풀었고 쉽기때문에 어렵지 않게 코드를 짰다.

우선 벡터에 입력을 넣는다. 1과 2가 연결되었다면 v[1]에 2를 삽입하고 v[2]에도 1을 삽입한다. 어느쪽이 부모일지 입력단계에선 미리 알 수 없기 때문이다.

bfs 단계에서는 루트인 1부터 자식 노드를 하나씩 방문하면서 그 자식노드에서도 연결된 모든 노드를 방문하며 방문한 노드의 parent가 누구인지 아직 정해지지 않았으면 지정하고 지정되어있으면 넘어가는 식으로 root부터 단말노드까지 모든 노드를 검사하고 출력하면 끝이다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EB%B6%80%EB%AA%A8%20%EC%B0%BE%EA%B8%B0(11725%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int N;
vector<int> v[100001];
int p[100001];

void bfs()
{
	queue<int> q;
	memset(p, -1, sizeof(p));
	q.push(1);
	p[1] = 1;
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int i = 0; i < v[here].size(); i++) {
			int next = v[here][i];
			if (p[next] == -1) {
				q.push(next);
				p[next] = here;
			}
		}
	}
}

int main()
{
	cin >> N;
	for (int a, b, i = 0; i < N-1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	bfs();
	for (int i = 2; i <= N; i++)
		cout << p[i] << "\n";
}