(백준 c++)11725 트리의 부모 찾기

문제

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

입력

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

출력

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

 

 

dfs로 트리의 부모를 찾았다.

메모리 초과가 날 수 있기 때문에 동적으로 각 노드별로 자식 노드를 넣어준다.

방문 여부를 알 수 있는 벡터와 각 노드의 부모를 저장하는 벡터를 각각 선언하여 사용.

 

루트 노드는 1이기 때문에 1부터 dfs 시작.

노드 1에 있는 자식 노드들을 dfs 탐색.

만약 자식 노드가 방문하지 않은 상태라면 true로 바꿔주고, 해당 자식 노드를 dfs 한다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> tree(100001);
vector<bool> visited(100001, false);
vector<int> parent(100001, 0);

void dfs(int start){
    for(int i = 0; i < tree[start].size(); i++){
        //루트부터 시작하여 자식 노드들 탐색
        int target = tree[start][i];
        
        //만약 자식 노드를 방문하지 않았다면 dfs 탐색
        if(!visited[target]){
            visited[target] = true;
            parent[target] = start;
            dfs(target);
        }
    }
}

int main(void){
    cin >> N;

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

    //루트가 1이기 때문에 루트부터 시작
    dfs(1);

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

    return 0;
}