[BOJ 11275 // C++] 트리의 부모 찾기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11275번 문제인 트리의 부모 찾기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

트리의 탐색은 일반 그래프의 탐색에 비해 편한 점이 있다.

들렀던 노드를 다시 들리지 않기 위해 방문한 노드인지 확인해야할 점이 부모노드 말고는 없다는 것이다.

따라서, 트리에서의 탐색은 구현을 비교적 간단히 할 수 있는 편이다.

자신의 부모노드가 있던 방향으로 탐색을 하지 않고 나머지 방향으로는 모두 탐색을 하면 된다.

 

또한, 트리의 루트를 정했을 때, 루트 노드를 제외한 모든 노드는 부모 노드를 딱 하나씩 가지게 된다.

따라서 루트에서부터 트리를 탐색(DFS, BFS등)하면서 자식노드의 다음 세대를 탐색하기 전에 기록하는 것으로 모든 노드의 부모를 한번에 구할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;

vector<int> G[100001];
int parent[100001];

void dfs(int root, int rootroot) {
    vector<int>::iterator iter = G[root].begin();
    while (!(iter == G[root].end())) {
        if (!(*iter == rootroot)) {
            parent[*iter] = root;
            dfs(*iter, root);
        }
        iter++;
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int x, y;
    for (int i = 1;i < N;i++) { // 그래프(트리) 만들기
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 2;i <= N;i++) {
        cout << parent[i] << '\n';
    }
    return 0;
}