Boj 11725 c++트리의 부모 찾기

https://www.acmicpc.net/problem/11725

 

어제 풀었는데 오늘 올린다.

 

문제는 다음과 같다. 

1부터 N까지의 연속된 수의 번호를 가진 노드들이 트리 형태로 존재한다.(간선이 N-1개이다.)

트리의 루트는 1이며,연결된 노드들에 대한 정보가 N-1개 주어질 때, 각 노드의 부모노드를 구하는 알고리즘을 만들어야 한다.

 

코드는 다음과 같다.

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

vector<int> visited(100001);
vector<vector<int>> arr(100001);
vector<int> parent(100001);
int N;



void find_parent(int V){
    visited[V]=1;
    for(int i=0; i<=arr[V].size()-1; i++){
        int next=arr[V][i];
        if(!visited[next]){
            parent[next]=V;
            find_parent(next);
        }
    }
}

int main(){

   cin>>N;

   for(int i=0; i<N-1; i++){
    int u, v;
    cin>>u>>v;
    arr[u].push_back(v);
    arr[v].push_back(u);

   }
   find_parent(1);
   for(int i=2; i<=N; i++){
    cout<<parent[i]<<"\n";

   }
}

 우선은 이중으로 벡터를 만들어 각 노드와 연결된 인접 노드에 대한 정보를 저장한다.

ex) arr[1]에는 1과 인접한 노드 { 2, 3...}의 벡터 형태로 저장된다.

그 후, 부모 노드 탐색 함수를 실행한다. 트리의 루트는 1이기에 1부터 시작한다. 함수의 실행 방식은 기존의 DFS방식 보다도 단순하다. 우선은 각 노드에 대해서 인접 노드에 대한 검사를 하고 방문되지 않은 노드에 대해서만 함수를 스택에 쌓는다. 이때, 하나의 노드에 대해서 다음으로 인접한 노드는 코드의 흐름상 해당 노드의 자식 노드이므로 부모 노드의 정보에 대한 인덱스 처리를 해준다. 

*하나의 노드에 대해서 자식 노드, 형제노드는 여러개일 수 있지만 부모노드는 한 개 뿐이기 때문에 인덱스가 충돌하지 않는다.

 

이후 2부터 N까지의 부모노드를 출력하면 끝난다.