백준 문제 풀이 - 트리의 부모 찾기 11725번

📜 문제 이해하기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

💡 문제 재정의

그래프가 트리의 형태로 주어질 때 각 노드의 부모 노드를 출력하라.

✏️ 계획 수립

dfs를 이용하면 쉽게 풀 수 있다.
노드들을 내려가면서 부모 노드를 저장하는 result 배열에 부모 노드를 삽입하고 내려가고 모든 재귀가 끝나면 result를 출력해주면된다.

💻 계획 수행

#include <bits/stdc++.h>

using namespace std;

int visited[100005];
vector<vector<int>> adj_list(100005);
int result[100005];

void dfs(int current_node){
    for (const int &node: adj_list[current_node]){
        if (visited[node] == 0){
            visited[node] = 1;
            result[node] = current_node;
            dfs(node);
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 0; i < N - 1; i++){
        int node1, node2;
        cin >> node1 >> node2;
        adj_list[node1].push_back(node2);
        adj_list[node2].push_back(node1);
    }
    dfs(1);
    for (int i = 2; i <= N; i++)
        cout << result[i] << '\n';
    return 0;
}

🤔 회고

원래는 파이썬으로 이 문제를 구현했지만 파이썬에서는 1000개 이상의 재귀를 하면 RecursionError가 발생하였다. 따라서 c++로 다시 구현하여 문제를 풀었다.