[백준] 11725번 트리의 부모 찾기 (C++)

 

 

목차

0. 서론

1. 문제 방향

2. 코드

 

0. 서론

---

문제

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

입력

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

출력

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

---

까지가 문제다.

필자가 푸는 시점에서는 실버2였고, 처음에 가닥을 잘못 짚어 조금 헤메었다.

 

1. 문제 방향

 필자의 생각 흐름이 궁금하지 않다면, 아래의 꺾어진구분선 아래부터 보면 된다.

필자는 처음에 union find와 경로압축의 변형버전이라고 생각했고, 

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

처럼 입력 받고, 하나하나 순회하며 vector에 부모를 찾아 넣었다.

재귀를 돌면서 1을 발견하면, 그 과정에서 발견한 번호들은 이미 부모를 찾았고, 부모를 찾지 못한 다른 노드에서 부모를 찾은 노드를 발견하면, 그 과정은 1과 연결되어있기에 그냥 부모로 갖다 넣었다.

 

이랬더니 시간초과가 났다. N이 무려 10만개까지 나올 수 있기 때문인듯 하다.

---

그래서 이 문제의 방향은, 특정 수 부터가 아닌, 1부터 시작하면 된다.

1과 연결된 모든 숫자는 1이 부모다.

1의 자식의 자식은, 1의 자식을 부모로 둔다.

 

-> 이렇게 되면, DFS BFS같은 탐색이 떠오른다.

 

 

이런 그래프가 있다고 가정하자.

 

1로 시작한 경우, 그 자식인 2와 3은 1을 부모로 두며, 배열에 이를 저장한다.

이제, 그 다음 수인 2를 선택하게 되면,

2의 탐색 대상은 1, 4, 5가 된다.

하지만, 2의 부모인 1을 건들게 되면 무한 루프가 걸리기에, 이를 제거해서 4,5를 봐야 한다.

 

아래 기술할 필자의 코드는 dfs의 재귀 코드에서 "그 전 값"을 확인하여 그냥 넘기도록 했지만, 이러한 방법 외에도 visited 배열을 만들어 이미 방문한 노드는 방문하지 않도록 해도 된다. 

 

여담으로 말하자면, visited 배열을 만드는것이 약 10%정도 빠른 결과가 나오는 듯 하다.

그럼 이렇게 부모가 찾아진다.

 

이러한 방법으로 풀면 정답이 나온다.

 

2. 코드

 

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

int N;
vector<vector<int>> table;
vector<int> parents;

void init() {
    int a,b;
    cin >> N;

    table.resize(N+1);
    parents.resize(N+1, 0);

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

void dfs(const int start, const int bef) {
    for(int target : table[start]) {
        if(target == bef) continue;
        parents[target] = start;
        dfs(target, start);
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    init();
    dfs(1,0);

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

    return 0;
}