[BOJ] 11725 - 트리의 부모 찾기 (C++)

문제

트리의 부모 찾기

코드

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int N;
unordered_map<int, int> up;
bool visited[1000001];

void make(int cur, vector<int> v[]){
    visited[cur] = true;
    for (int i = 0; i < v[cur].size(); i++){
        if (visited[v[cur][i]]) continue;
        up[v[cur][i]] = cur;
        make(v[cur][i], v);
    }
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> N;
    vector<int> adj[N+1];
    int x, y;
    for (int i; i < N-1; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    make(1, adj);

    // up에서 찾기
    for (int i = 2; i <= N; i++) cout << up[i] << "\n";
    return 0;
}

분석

한 노드의 인접한 노드는 자식이거나 부모일 것이다. 트리의 루트는 1로 정해져 있으니 루트부터 bfs탐색을 하면서 나오게 되는 노드들은 현재 노드의 자식일 것이다. 이를 up에 저장하여 노드의 부모를 가리키게 하였다.