[백준 / C++] 트리의 부모 찾기 (실버 2, 11725)

https://www.acmicpc.net/problem/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

예제 입력 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

---

문제 풀이

이 문제는 트리 구조에서 부모 노드를 찾는 전형적인 문제로, DFS(깊이 우선 탐색)를 이용하여 해결할 수 있습니다. DFS를 통해 트리를 순회하면서 각 노드의 부모 노드를 기록하는 방식으로 진행됩니다.

문제를 해결하는 과정을 요약하면 다음과 같습니다:

1. 트리 입력: 먼저, 간선 정보를 입력받아 트리 구조를 구성합니다. 트리는 무방향 그래프이므로 각 간선은 양방향으로 연결됩니다.
2. DFS 탐색: DFS를 사용하여 1번 노드부터 시작해 자식 노드를 탐색합니다. 이때 자식 노드가 방문되지 않았으면, 해당 노드의 부모 노드를 기록하고 재귀적으로 계속 탐색을 진행합니다.
3. 결과 출력: DFS 탐색이 완료되면 2번부터 N번까지 각 노드의 부모 노드를 출력합니다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[100002];
int n;

int visited[100002];

void DFS(int u)
{
	for (int v : adj[u])
	{
		// 방문 체크
		if (visited[v]) continue;

		visited[v] = u;
		DFS(v);
	}
}

int main()
{
	cin >> n;

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

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

	DFS(1);

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