[BOJ] 11725 트리의 부모 찾기 c++ (트리 특징, dfs)

 

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

 

✔ 문제 이해

루트노드가 1인 트리가 있다. 2부터 N까지 노드들의 부모노드를 순서대로 출력하라.

 

✔ 풀이 + 코드

자식노드부터 찾으려고 해서 답을 찾지 못했다. 트리는 부모노드부터 탐색하면 자식노드 모두를 탐색할 수 있다는 특징을 갖고 있다.

이를 사용하여 부모노드부터 타고 내려가 모든 자식노드들의 부모노드를 현재 방문하고 있는 노드로 설정해주면 된다.

 

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

int N, a, b;
vector<int> board[100004];
bool visited[100004];
int arr[100004];

void dfs(int n)
{
    visited[n] = 1;

    for(int i = 0; i < board[n].size(); ++i)
    {
        int next = board[n][i];
        if(!visited[next]){
            arr[next] = n;
            dfs(next);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 0; i < N-1; ++i){
        cin >> a >> b;
        board[a].push_back(b);
        board[b].push_back(a);
    }

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

    return 0;
}

 

✔ 피드백

• 트리는 부모노드부터 탐색한다면 모든 노드를 방문할 수 있고, 그 전 노드(지나친 부모노드)를 신경쓰지 않아도 된다.

✔ reference

https://ongveloper.tistory.com/164