[백준] 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로 생각해보면, 1 6이 입력된다면 6의 부모노드는 1이 되는 것이다.

인접리스트로 원소를 추가하여 그려보자

 

해당 노드
1	->	6	->	4
2	->	4
3	->	6	->	5
4	->	1	->	2	->	7
5	->	3
6	->	1	->	3
7	->	4

 인접리스트의 해당 노드의 바로 다음 원소가 부모노드가 됨을 알 수 있다.

이 아이디어로 코드를 구현하면 된다

 

코드

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> tree[100001];
int parent[100001];

void DFS(int node) { // 시작은 1번 노드의 부모 찾기부터
	//인접리스트의 해당 노드들의 다음 노드 값이 부모
	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i]; // 바로 해당 노드의 다음 원소를 next노드라고 하고,
		if (parent[next] == 0) { // parent배열에 아직 부모노드로 지정이 안되어 있다면 해당노드를 부모노드라고 지정
			parent[next] = node; // 만일 이미 부모노드가 배열에 지정되어 있다면, 부모노드가 아니다.
			DFS(next);
		}
	}
}
// 인접리스트 형태로 각 노드를 저장
int main() {
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		int x, y;
		cin >> x >> y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	DFS(1); //  1번 노드부터 N번 노드까지 각 노드의 부모를 찾기
	for (int i = 2; i <= N; i++) { // 1번 노드는 루트임으로 제외하고 부모 출력
		cout << parent[i] << '\n';
	}
	return 0;
}

 

 

출처

• 문제를 만든 사람: baekjoon
• 잘못된 조건을 찾은 사람: jh05013