백준 11725번 - 트리의 부모 찾기

백준 11725번 - 트리의 부모 찾기

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

문제

• 루트 없는 트리가 주어진다.

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

입력

• 첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.

• 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

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

접근

• parent 배열을 만들어 입력된 정점 중 부모노드를 찾아 바로 기록해준다.

• 부모노드는 parent 배열에 기록된 적이 있는 노드가 부모노드가 된다.

• 입력의 순서때문에 두 정점이 모두 부모가 없는 경우가 있는데 이 때, 스택을 활용하여 따로 빼두었다가 나중에 다시 검사한다.

• 큐를 사용했더니 시간초과가 떴다. 매 번 같은 방향으로만 검사를 해서 그런 듯.

• 큐 대신 스택 2개를 활용하여 방향을 바꿔가며 검사를 하면 짧은 시간에 풀 수 있다.

C++ Code

#include <cstdio>
#include <stack>
using namespace std;
​
int parent[100001] = { 0 };
int n;
int a, b;
stack<pair<int, int>> s[2];
int idx = 0;
​
int main(void) {
    scanf("%d", &n);
    parent[1] = 1;
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &a, &b);
        if (parent[a]) parent[b] = a;
        else if (parent[b]) parent[a] = b;
        else s[idx].push({ a, b });
    }
​
    while (!s[0].empty() || !s[1].empty()) {
        auto t = s[idx].top();
        a = t.first; b = t.second;
        s[idx].pop();
        if (parent[a]) parent[b] = a;
        else if (parent[b]) parent[a] = b;
        else s[1 - idx].push({ a, b });
        if(s[idx].empty()) idx = 1 - idx;
    }
​
    for (int i = 2; i <= n; i++) {
        printf("%d\n", parent[i]);
    }
    return 0;
​
}