트리의 부모 찾기

문제: 트리의 부모 찾기 (백준 11725번)

구조 분석

해당 문제를 처음 접하고 매우 당황했다. 지금까지는 트리문제는 트리구조를 만들고 이를 순회하며 탐색하는 경우만 접했기 때문에 루트노드와 자식노드가 정해져있지 않은 트리를 어떻게 만들어야 할 지 감이 안왔기 때문이다.

우선 노드 별로 연결된 노드를 저장하기 위해 vector list를 생성하여 입력을 받도록 했다.

// Create list whose element is vector
vector<int> V[100001];

이후 dfs나 bfs를 이용하여 root로부터 순회하는 프로그램을 짜면 된다.

풀이 방법

우선 vector list에 각 노드별로 연결된 노드들을 전부 저장한다. 이후 dfs 또는 bfs 탐색을 통해서 1번 노드부터 연결된 노드들로 expand를 실시하며 각 노드의 parent를 저장하면 된다.

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n;
// Vector List
vector<int> V[100001];
stack<int> S;
int root[100001];
int visited[100001];

void dfs() {
    while(!S.empty()) {
        int x = S.top();
        S.pop();
        for (int i=0; i<V[x].size(); i++) {
            int next = V[x][i];
            if (root[x] == next) continue;
            S.push(next);
            root[next] = x;
        }
    }
}

int main() {
    cin >> n;
    int n1, n2;
    for (int i=0; i<n-1; i++) {
        cin >> n1 >> n2;
        V[n1].push_back(n2);
        V[n2].push_back(n1);
    }
    S.push(1);
    dfs();
    for (int i=2; i<=n; i++) {
        cout << root[i] << "\n";
    }
    return 0;
}  

정리

Tree는 자료구조일 뿐 이는 탐색하는 알고리즘이 아니라는 것을 알아두자. 물론 tree 순회를 통해 find를 실시할 수 있지만 문제풀이를 위한 탐색에는 dfs나 bfs가 이용될 수 있음을 명심하자. 또한 tree를 저장하기 위해서 stl vector를 자유롭게 이용할 수 있어야 한다고 생각한다.

// Vector which has 100 elements
vector<int> V(100)

// Vector list which has 100 vector elements
vector<int> V[100]  

위 두가지를 헷갈리지 말자.