BOJ 11725 - 트리의 부모 찾기 문제풀이

문제를 읽고 이해하기

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

 

입력

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

 

출력

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

 

재정의와 추상화

DFS, BFS 개념을 알고 있는 상태에서 직접 그래프를 그려보면 금방 풀 수 있는 문제이다. 먼저 해당 정점의 부모를 저장하는 int형 mother[100001]이라는 배열을 선언한다. DFS, BFS를 돌면서 현재 노드의 번호를 now라고 하고, now와 연결된 노드의 번호를 next라고 하였을 때, mother[next] = now; 구문을 매 탐색마다 시행하면 된다.

 

코드 작성

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

vector<int> v[100001];
bool check[100001];
int mother[100001];

void dfs(int start) {
    stack<int> s;
    s.push(start);
    check[start] = true;

    while(!s.empty()) {
        auto now = s.top();
        s.pop();

        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i];
            if (!check[next]) {
                s.push(now);
                s.push(next);
                check[next] = true;
                mother[next] = now;
                break;
            }
        }
    }
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

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

    dfs(1);
    for (int i = 2; i <= n; i++)
        cout << mother[i] << '\n';

    return 0;
}