[BOJ] 11725번 : 트리의 부모 찾기 (C++)

📖 백준 11725번 : https://www.acmicpc.net/problem/11725

문제

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

입력

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

출력

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

---

풀이

모든 노드는 연결되어 있음이 보장되고 루트노드는 항상 1이다. 따라서 예외적인 상황을 신경쓰지 않고 단순히 그래프 탐색으로 접근했다. 각 노드를 양방향으로 연결해 저장하고, dfs를 사용해 탐색하면서 방문할 노드의 부모를 myParent배열에 저장하는 방식으로 풀었다. 단, 주의해야하는 점은 dfs를 시작하는 위치가 루트노드여야 한다.

코드

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

int n;
vector<int> graph[100001];
bool visited[100001];
int myParent[100001];

void dfs(int start) {
    visited[start] = true;

    for (int i = 0; i < graph[start].size(); i++) {
        int x = graph[start][i];
        if (!visited[x]) {
            myParent[x] = start;
            dfs(x);
        }
    }
}

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

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

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

    return 0;
}