[BOJ_C++] 11725번 : 트리의 부모 찾기

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

#define MAX 100001

int parent[MAX]; 
vector<int> tree[MAX];

void search(int node) {
    for (int i = 0; i < tree[node].size(); i++) {
        if (parent[tree[node][i]] == 0) {
            parent[tree[node][i]] = node;
            search(tree[node][i]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    parent[1] = 1;

    int n; cin >> n;
    int temp1, temp2;
    for (int i = 1; i < n; i++) {
        cin >> temp1 >> temp2;
        tree[temp1].push_back(temp2);
        tree[temp2].push_back(temp1);
    }

    search(1);

    for (int i = 2; i <= n; i++)
        printf("%d\n", parent[i]);
    
    return 0;
}

• 입력을 받을 때 앞에 입력받은 노드가 부모인지 자식인지 모르기 때문에 각 노드 백터에 원소 맨 뒤로 가도록 원소들을 추가해준다.
• search() 함수는 부모를 찾는 함수이며 dfs를 사용한다.
• 이때 dfs를 사용하는 이유는 1이 루트 노드라고 알려주었으므로 1과 이어진 노드들이 서브 트리의 부모가 되고 그 노드들과 이어진 노드들이 다른 서브 트리의 부모가 되는 것이기 때문이다.
• search() 함수에서는 parent[tree[node][i]]가 0이면 해당 노드의 부모를 아직 찾지 못한 것이다. 따라서 node가 부모라는 것을 알려주고, 그 tree[node][i]가 부모가 되는 서브트리를 탐색하는 것을 반복하게 된다.

결과