[baekjoon 11725] 트리의 부모 찾기- 트리, 그래프, BFS, DFS (C++)

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

루트는 1로 고정되어있고, 각 노드들의 부모를 출력하면 되는 문제이다.

 

일단 벡터를 통해 양 노드의 값을 저장해주고, DFS탐색을 노드 1부터 해준다.

 

트리의 특성상 리프 노드를 제외하고 연결되어 있으므로 연결된 노드를 통해 탐색해주면서, 부모를 저장해준다.

현재 x노드를 방문한 상태에서 x와 연결된 y가 아직 방문되지 않았다는 것은 y는 x의 자식 노드라는 의미이다.

 

방문하지 않았다면 DFS(연결된 다음 노드)를 진행해주면서 parent [연결된 다음 노드] = 현재 노드를 해주면 된다.

 

ex) 예제 입력이

7

1 6

6 3

3 5

4 1

2 4

4 7

이면

vector에 저장은 밑의 표처럼 저장이 되고(연결 정보를 표시)

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

부모 테이블은 밑의 표처럼 구성이 된다.

1	2	3	4	5	6	7
루트	4	6	1	3	1	4

vector에 입력받은 순서대로 재귀를 진행해보면 (첫 번째 표를 따라가면서 읽으면 된다)

루트와 연결된 노드부터 루트의 자식으로 계산하면서 진행해준다.

1. 루트노드인 1부터 DFS(1) -> DFS(6) 방문하면서 parent[6] = 1

2. DFS(6) -> DFS(1) 이미 방문 -> DFS(3) 방문하면서 parent[3] = 6

3. DFS(3) -> DFS(6) 이미 방문 -> DFS(5) 방문하면서 parent[5] = 3

4. DFS(5) -> DFS(3) 이미 방문 -> 2, 3, 4 DFS는 종료 -> 다시 1번으로

 

5. DFS(1) -> DFS(4) 방문하면서 parent[4] = 1

6. DFS(4) -> DFS(1) 이미 방문 -> DFS(2) 방문하면서 parent[2] = 4

7. DFS(2) -> DFS(4) 이미 방문 -> 다시 6번으로

 

8. DFS(4) -> DFS(2) 이미 방문 -> DFS(7) 방문하면서 parent[7] = 4

9. DFS(7) -> DFS(4) 이미 방문 -> 나머지 DFS 재귀 종료되면서 탐색 종료

#include <iostream>
#include <vector>

using namespace std;

int n, from, to, parent[100001], check[100001];
vector<int> v[100001];

void DFS(int start) {
	check[start] = true;
	for (int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];
		if (!check[next]) {
			parent[next] = start;
			DFS(next);
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}

	DFS(1);

	for (int i = 2; i <= n; i++) {
		cout << parent[i] << "\n";
	}
}