백준 11725 트리의 부모 찾기 / C++

문제 : 11725

풀이 point

트리를 그리기 위해 그래프 자료구조 인접리스트를 활용한다.
트리의 루트가 1이라고 했으므로 1부터 탐색을 진행한다.

다음 탐색 노드의 부모는 바로 전 탐색한 노드가 된다.
이 알고리즘을 생각하며 구현해보자.

양방향 그래프로 그려야한다.(부모가 왼쪽 입력으로 들어온다는 보장이x)

풀이 방법

dfs를 활용할 수 있다.

예제 입력 1
ex) 1 : 6,4
2 : 4
3 : 5, 6
4 : 1, 2, 7
5 : 3
6 : 1, 3

이 경우 1을 탐색할 때 자식 노드로는 6과 4가 있다.
6의 부모는 1로 설정해두고 dfs이기 때문에 6과 관련된 노드 1, 3으로 간다.
visit배열을 통해 노드를 방문했는지 기록했기 때문에 1은 방문하지 않는다.
다음 노드인 3으로 간다. 3의 부모는 6으로 설정해둔다.
이렇게 순차적으로 모든 노드가 방문되었으면 부모 노드도 모두 설정이 되어있는 상태이다.

코드

//백준 11725, 트리의 부모 찾기

#include <iostream>
#include <vector>

std::vector<int> graph[100'001];
int visit[100'001];
int parents[100'001];

void dfs(int k){
    visit[k] = true;
    for(auto g : graph[k]){
        if(visit[g]) continue;
        visit[g] = true;
        parents[g] = k; 
        dfs(g);
    }
}

int main (){

    int N;
    std::cin >> N;

    for(int i{1}; i<N; ++i){
        int a, b;
        std::cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1);

    for(int i{2}; i<=N; ++i) std::cout << parents[i] << '\n';

    return 0;
}