[백준/C++] 11725번 : 트리의 부모 찾기 (DFS/BFS 연습)

트리의 부모 찾기 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 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

예제 입력 2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2

1
1
2
3
3
4
4
5
5
6
6

---

주어진 입력이 트리의 부모노드와 자식노드로 따로 구분되어있지 않기 때문에, 양방향 그래프를 작성해주었다.

 

예제 입력이 위와 같이 주어졌을 때, 

1과 6을 입력받으면 tree[1] = 6, tree[6] = 1을 각각 초기화하여 양방향 그래프로 만들었다.

 

이후엔 DFS 또는 BFS를 활용하여 부모노드를 찾으면 되는데 나는 DFS(깊이 우선 탐색) 방법을 사용하였다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;
vector<vector<int>> tree;
int parent[100001];

void DFS(int node)
{
	for(int i = 0; i < tree[node].size(); i++)
	{
		int next = tree[node][i];
		if(parent[next] == 0)
		{
			parent[next] = node;
			DFS(next);
		}
	}
}

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

	int N;
	cin >> N;
	tree.resize(N+1);
	for (int i = 0; i < N-1; i++)
	{
		int temp1, temp2;
		cin >> temp1 >> temp2;
		tree[temp1].emplace_back(temp2);
		tree[temp2].emplace_back(temp1);
	}

	DFS(1);	

	for (int i = 2; i <= N; i++)
		cout << parent[i] << '\n';

	return 0;
}

 

문제에서 루트노드를 1으로 둔다고 했기 때문에, 노드 1부터 DFS 탐색을 시작하였다.

 

트리의[node] 에 존재하는 원소를 for문으로 탐색하면서, 다음 노드가 존재하는데 부모 노드 배열(parent[100001])이 초기화되어 있지 않다면, 현재 노드를 부모로 설정하고 다음 노드를 또 DFS 탐색하도록 하였다.

 

문제 자체는 매우 간단한 DFS 문제였지만, 트리 노드들의 입력 값을 받아 양방향 그래프로 작성하고 부모를 찾아가는 방식이 인상깊어서 게시글로 정리해보았다.

---

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

11725번: 트리의 부모 찾기