BOJ - 11725번 트리의 부모찾기

문제 출처: https://jaimemin.tistory.com/585

문제 난이도

Silver 2 (solved.ac 이용)

문제 접근법

1. 트리 모양으로 밑으로 퍼지는 구조이다.
2. 그렇기 때문에 부모노드를 알려면 마지막 자식노드까지 탐색해야한다.
3. 깊이 탐색할 수 있는 알고리즘은? DFS

루트를 1이라 항상 가정하기 때문에 시작은 1로 하고 DFS를 하면 된다.

통과 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> tree[100001];
int check[100001];
int parentNode[100001];

void DFS(int x) {
	check[x] = true;

	for (int i = 0; i < tree[x].size(); i++) {
		int nx = tree[x][i];
		if (check[nx]) continue;
		parentNode[nx] = x;
		DFS(nx);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	DFS(1);
	for (int i = 2; i <= N; i++) {
		cout << parentNode[i] << "\n";
	}
	return 0;
}

피드백

트리 관련한 문제는 풀이법이 잘 안떠오른다. 자료구조 수업 들을 때 C로 일일이 함수 구현하면서 했던게 너무 괴로웠는지..ㅜ 알고리즘 문제로 나올 수 있으니 골고루 풀어놔야겠다