[BOJ] #11725 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

---

간단한 문제인거 같은데, 생각보다 많이 헤맸다...

일단 가중치 없는 그래프 탐색이니 BFS 문제로 갈피를 잡고 들어갔으나, 각 인덱스 마다 계속 BFS를 하는것으로 방향을 잡고 풀다가 계속 틀렸다. 이유인 즉, 자식노드가 복수일 경우에는 해당 방법으로는 절대 부모노드를 구할 수 없기 때문이다. 따라서, 그냥 루트 노드 1에서부터 BFS를 한번만 돌리는 방향으로 바꾸어 풀었다. 처음에 왜 이 생각을 못했을까 싶다. 생각해보면 정말 당연한건데 말이다.

부모노드를 찾는것이기 때문에 부모노드들의 부모노드. 즉, 루트노드인 1에서부터 출발하여 BFS를 돌리면 아주 쉽게 그 밑에 있는 자식노드들을 구할 수 있다. 그럼 탐색을 돌리는 와중에 발견되는 자식노드들을 그때그때 정답을 저장해놓는 배열인 ANS에 저장해놓고 마지막에 한번에 출력만 해주면 된다.

사실 정말 당연한 이치이지만, 그 당연한 이치를 떠올리지 못해 많이 헤맨 문제였다. 앞으로 비슷한 문제가 나오면 무조건 루트노드를 시작점으로 잡고 접근해야할듯 하다.

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

#define MAX 100005

using namespace std;

int N;
vector<int> Graph[MAX];
int ANS[MAX];
bool visited[MAX] = { false };

void BFS(int start) {
    queue<int> Q;
    Q.push(start);
    visited[start] = true;

    while (!Q.empty()) {
        int parent = Q.front();
        Q.pop();

        for (int i=0; i<Graph[parent].size(); i++) {
            int child = Graph[parent][i];

            if (!visited[child]) {
                Q.push(child);
                visited[child] = true;

                ANS[child] = parent;
            }
        }
    }
}

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

    cin >> N;

    for (int i=0; i<N-1; i++) {
        int a, b;
        cin >> a >> b;

        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    BFS(1);

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

    return 0;
}

수많은 시행착오의 흔적들..