[백준 11725번] [트리] 트리의 부모 찾기

처음에는 이중배열을 만들어서 1번부터 node를 설정해주는 방향으로 진행하였다.

하지만, 숫자가 십만이므로 이렇게 사용하게 되면 100000 * 100000 * 4 = 40G(10^9 바이트가 1기가이므로) 가 나오고 메모리 초과가 뜬다.

 

이를 해결하기 위해 골똘히 고민해보니까

가질 수 있는 노드들의 갯수가 제한되어있으므로 해당 노드들만 저장하면 된다는 것을 파악하였다.

 

그리고 visited를 사용하여 방문한 노드들을 따로 제거해주면 상위 노드를 다시 방문하는 일은 발생하지 않는다.

 

위의 알고리즘을 활용하여 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int visited[100001] = {0};
int parent_store[100001] = {0};

void make_tree(const vector<vector<int> > &data_store, int start){
    int length = data_store[start].size();
    visited[start] = 1;
    
    for(int i = 0; i < length; i++){
        if(visited[data_store[start][i]] != 1){
            parent_store[data_store[start][i]] = start;
            make_tree(data_store, data_store[start][i]);
        }
    }
    return;
}

int main(void){
    int n;
    cin >> n;

    vector<vector<int> > data_store(n + 1);
    for(int i = 0; i < n; i++){
        vector<int> temp;
        data_store[i] = temp;
    } // initialize

    for(int i = 0; i < n - 1; i++){
        int first, second;
        cin >> first >> second;
        data_store[first].push_back(second);
        data_store[second].push_back(first);
    } // node_store

    make_tree(data_store, 1);

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

    return 0;
}