백준 11725. 트리의 부모 찾기

알고리즘 기초 문제 중 620 - 트리

트리의 부모 찾기

1. 간단 설명

루트가 없는 트리가 주어진다

트리의 루트를 1이라 정했을 때, 각 노드의 부모를 구하는 문제

2. 예시

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

루트가 1이므로 다음과 같은 트리가 만들어진다

1 
|\
4 6
|\ \
2 7 3
     \
	  5

2번 노드부터 부모를 출력하면

4 6 1 3 1 4 이다

3. 알고리즘

문제 설명이 상당히 친절하지 않은 편이다

예제 1, 2만 봐서는 이진 트리처럼 보인다

또한, 1번 노드부터 순서대로 주어지므로,

부모 자식을 구분한 뒤에 부모를 구분하면 되면 해결 될 것 처럼 보인다.

그러나 실제로는

3
2 3
1 2

와 같은 입력이 주어질 수도 있고

5
2 3
2 4
2 5
1 2

와 같이 이진 트리가 아닌 입력이 주어질 수도 있다

즉, 일단 그래프로 가정하고 입력받은뒤, 이를 DFS 혹은 BFS로 정석적으로 탐색하는게 적절해보인다

1. 그래프 연결 정보를 저장한다
2. 1번 노드부터 탐색하면서, 각 노드의 부모 노드를 체크한다
3. 2번 노드부터 N번 노드까지 부모 노드를 출력한다

4. 소스코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define MAX 100001

int N;

vector<int> graph[MAX];
int visited[MAX];
int parent[MAX];

void BFS() {
	queue<int> qu;
	qu.push(1);

	while (!qu.empty()) {
		int now = qu.front();
		qu.pop();

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if (visited[next] != 0) continue;
			visited[next] = 1;
			parent[next] = now; // 부모 정보 기록
			qu.push(next);
		}
	}
}

void DFS(int cur) { 
	
	visited[cur] = 1;

	for (int i = 0; i < graph[cur].size(); i++) {
		int next = graph[cur][i];
		if (visited[next] != 0) continue;
		
		parent[next] = cur;
		DFS(next);
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	// 그래프 연결 정보 저장
	graph->resize(N + 1);
	for (int i = 0; i < N - 1; i++) {
		int start, end; cin >> start >> end;
		graph[start].push_back(end);
		graph[end].push_back(start);
	}

	// 2. 1번 노드부터 탐색하면서 각 노드의 부모 노드를 체크
	DFS(1);
	// or BFS();

	// 3. parent 배열의 2번부터 N번까지 쭉 출력
	for (int i = 2; i <= N; i++) {
		cout << parent[i] << '\n';
	}

	return 0;
}

배운점

예제에 나오지않은 히든 테케도 직접 고려하면서 알고리즘을 작성해볼 것