[BOJ] 트리의 부모 찾기 11725번 C++

 

 

문제

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

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

접근 방식

 

트리의 간선 정보를 이용해 부모-자식 간의 관계를 파악해야 한다.

이때, 루트를 1을 기준으로 했을 때를 주의할 것!

 

간단하게 DFS(깊이 우선 탐색)을 이용해 관계를 파악할 수 있는데

루트노드인 1을 기준으로 자식들을 탐색하면서 확인하면 된다.

이때, 1의 자식노드들을 탐색할 때, 4와 6이 연결되어 있다면

4와 6의 부모는 1이기 때문이 이를 부모 배열에 따로 저장해주면 된다!

 

 

코드

#include<bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> tree;
vector<int> parent;

void dfs(int node, int par) {
    parent[node] = par;

    for(int nxt : tree[node]) {
        if(nxt != par) {
            dfs(nxt, node);
        }
    }
}

int main() {
    cin>>N;
    tree.resize(N+1);
    parent.resize(N+1);

    for(int i=0; i<N; i++) {
        int a,b; cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    dfs(1,0);

    for(int i=2; i<=N; i++) cout<<parent[i]<<'\n';
}