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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

트리의 부모 찾기

문제

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

풀이

먼저 온갖 꼼수(?)를 써보려고 이리저리 수정했지만, 결국에는 처음 생각한 풀이가 맞았다.

 

이 문제는 각 노드의 부모가 모르는 상태로 그저, 각 노드의 연결 정보만 입력으로 주어진다.

정확히는, 트리의 루트는 1이고, 나머지 노드는 부모를 모르는 상태로 주어진다.

 

일단, 트리의 정의를 보자.트리는 사이클이 발생하지 않는 그래프이다.

 

그러니, 우선 노드들의 정보를 그래프로 받아온다.그 다음, BFS(또는 DFS)로 탐색을 진행한다.탐색을 진행할 때, 각 노드로 오기 이전의 노드가 부모가 된다. << 이 부분이 핵심.

 

1) BFS 풀이

#include <iostream>
#include <vector>
#include <queue>

#define endl '\n'

using namespace std;

vector<int> tree[100001];
bool visited[100001];
int parents[100001];

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

    int N;
    cin >> N;

    int a, b;
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    queue<int> q;
    q.push(1);
    visited[1] = true;

    while (!q.empty()) {
        int n = q.front();
        q.pop();

        for (int i = 0; i < tree[n].size(); i++) {
            if (!visited[tree[n][i]]) {
                q.push(tree[n][i]);
                parents[tree[n][i]] = n;
                visited[tree[n][i]] = true;
            }
        }
    }

    for (int i = 2; i <= N; i++) {
        cout << parents[i] << endl;
    }

    return 0;
}

 

2) DFS 풀이

#include <iostream>
#include <vector>

#define endl '\n'

using namespace std;

vector<int> tree[100001];
bool visited[100001];
int parents[100001];

void DFS(int n) {
    visited[n] = true;

    for (int i = 0; i < tree[n].size(); i++) {
        if (!visited[tree[n][i]]) {
            parents[tree[n][i]] = n;
            DFS(tree[n][i]);
        }
    }
}

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

    int N;
    cin >> N;

    int a, b;
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    DFS(1);

    for (int i = 2; i <= N; i++) {
        cout << parents[i] << endl;
    }

    return 0;
}