백준 11725 트리의 부모 찾기

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

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

---

[풀이 과정]

문제를 손으로 그려보면서 생각난 풀이 방법은 dfs를 돌리면서 현재 위치에서 갈 수 있는 정점은

'arr[갈수있는 정점] = 현재 위치' 를 해주는 것이었다.

 

1. 입력을 받고 graph벡터에 정점들의 연결을 표시한다.

 

2. graph를 오름차순으로 정렬한다.

 

3. dfs(int start) : 현재 위치에서 갈 수 있는 정점을 찾는다.

-  아직 방문하지 않은 곳이면 arr[next] = start를 해준다.

 

4. dfs가 종료되면 2번 정점부터 n번 정점 순서로 부모를 출력한다.

---

[소스 코드]

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100005;
int n;
vector <int> graph[MAX];
int arr[MAX];

void dfs(int start) {
	for (int i = 0; i < graph[start].size(); i++) {
		int next = graph[start][i];

		if (!arr[next]) {
			arr[next] = start;
			dfs(next);
		}
	}
}
int main() {
	scanf("%d", &n);

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for (int i = 1; i <= n; i++) sort(graph[i].begin(), graph[i].end());

	dfs(1);

	for (int i = 2; i <= n; i++) printf("%d\n", arr[i]);
	return 0;
}

https://github.com/chojaehyo/CodingTest/blob/main/%5BBOJ%5D%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EB%B6%80%EB%AA%A8%20%EC%B0%BE%EA%B8%B0

GitHub - chojaehyo/CodingTest