(C++) - 백준(BOJ) 11725번 : 트리의 부모 찾기 답

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

풀이방법

 1. 입력을 받습니다. 받을 때 정점 사이의 간선들이 주어지므로 정점 n개를 가진 tree자료구조에서 간선들의 개수는 n-1개입니다. 따라서 그만큼 입력을 받고 vector에는 인접행렬 형식으로 양방향 간선을 추가해줍니다.

 2. parent[x] 는 x정점의 부모에 해당하는 정점 번호가 값으로 들어갑니다. root node로부터 시작, 각 정점에 연결된 간선을 정보를 따라 만약 갱신되지 않은 부모배열 방이 있다면 갱신해줍니다. 즉,

vector[1]이라는 정점에 연결된 정점들이 2,3,4라면 parent[2], parent[3], parent[4] 의 부모는 1번 정점이 되도록 갱신됩니다. 그 후 다음 정점 2,3,4를 부모로 한 다른 정점들을 탐색하기 위해 해당 재귀함수를 호출합니다. 이렇게 함으로써 root node를 제외한 모든 node는 parent정점을 가지게 됩니다.

 3. 재귀함수 dfs는 for문을 다 돌면 자동으로 종료되므로 모든 정점을 탐색한 후에는 결과를 root node를 제외한 2번 정점부터 parent배열을 출력해주면 됩니다.

 

Code

#include <iostream>
#include <vector>
using namespace std;

int n;
int parent[100001];
vector <int> v[100001];

void dfs(int x){
    for(int i = 0; i < v[x].size(); i++){
        if(!parent[v[x][i]]){
            parent[v[x][i]] = x;
            dfs(v[x][i]);
        }
    }
}

int main(){
    cin >> n;
    for(int i = 0; i< n-1; i++){
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    dfs(1);
    for(int i = 2; i<= n; i++){
        cout << parent[i] << '\n';
    }
}