[C++ 백준 풀이] 11725번 : 트리의 부모 찾기 (벡터 활용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 Class 4 문제들에 해당하는 11725번 : 트리의 부모 찾기에 대한 풀이 코드와 해설을 포함하고 있습니다.

 

이번 문제에서는 그래프 문제들 중에서도 C언어로는 메모리 문제 때문에 해결하기 어려운 문제들을 C++의 벡터를 활용하여 쉽게 해결해보도록 하겠습니다.

 

 

11725번 : 트리의 부모 찾기

 

이 문제는 그래프의 노드들에 대한 정보를 배열에 저장할 경우 메모리 초과가 발생하게 됩니다.

따라서 메모리를 더욱 아끼기 위한 방법으로 벡터를 사용하는 것이 바람직합니다.

C에서도 충분히 메모리를 아끼는 작은 크기의 배열로 해결이 가능은 하겠지만, 그러기에는 이 문제에 너무 오랜 시간이 들기 때문에 C++의 헤더파일을 사용하는 것이 좋습니다.

 

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

vector<int> line[100005];
int visited[100005] = {0, }, parent[100005];

void DFS(int v) {
    visited[v] = 1;
    for(int i=0; i<line[v].size(); i++)
        if(!visited[line[v][i]]) {
            parent[line[v][i]] = v;
            DFS(line[v][i]);
        }
}

int main() {
    int N, a, b;
    cin >> N;
    for(int i=0; i<N-1; i++) {
        cin >> a >> b;
        line[a].push_back(b);
        line[b].push_back(a);
    }
    DFS(1);
    for(int i=2; i<=N; i++) cout << parent[i] << '\n';
}

 

벡터는 사용할만큼만의 메모리를 할당받아 사용하기 용이하기 때문에 이런 문제를 풀 때 유용합니다.

이 문제에서는 최상위 노드가 1이라는 강력한 조건이 붙어있기 때문에 1번 노드에서부터 DFS(또는 BFS)를 수행해나가면 새로운 노드가 발견될 때마다 그것이 현재 노드의 자식 노드임을 알 수 있습니다.

따라서 visited가 체크되지 않은 노드가 발견되면, 그 노드의 parent를 현재 위치로 저장하면 됩니다.

탐색이 끝난 이후에는 parent에 저장된 원소를 하나씩 출력해주면 됩니다.

 

 

풀이 시간은 약 100ms 정도로 안정적인 시간 내에 수행되는 것을 확인할 수 있습니다.