[백준/C++] 11725번: 트리의 부모찾기

11725번: 트리의 부모찾기 문제 바로가기

문제 분석

노드의 개수와 연결된 두 정점이 주어질 때,

2번 노드부터 순서대로 해당 노드의 부모 노드 번호를 출력하면 되는 문제

---

문제 풀이 과정

1. 연결된 두 정점이 입력으로 주어질 때, 트리 구조를 만들자.

   for (int i = 0, x, y; i < N - 1; i++) {
           cin >> x >> y;
           t[x].push_back(y);
           t[y].push_back(x);
       }

2. dfs를 돌면서 해당 노드의 부모 노드 번호를 담자.

   void dfs(int n) {
       check[n] = true;
       for (int i = 0; i < t[n].size(); i++) {
           int nxt_n = t[n][i];
           if (check[nxt_n]) continue;
           ans[nxt_n] = n;  // ans[해당 노드] = 부모 노드 번호
           dfs(nxt_n);
       }
   }

3. dfs가 다 끝나면, 2번 노드부터 순서대로 출력하자.

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

---

코드

#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;

int N;
vector <int> t[MAX];
bool check[MAX];
int ans[MAX];

void dfs(int n) {
    check[n] = true;
    for (int i = 0; i < t[n].size(); i++) {
        int nxt_n = t[n][i];
        if (check[nxt_n]) continue;
        ans[nxt_n] = n;
        dfs(nxt_n);
    }
}

int main() {
    cin >> N;
    for (int i = 0, x, y; i < N - 1; i++) {
        cin >> x >> y;
        t[x].push_back(y);
        t[y].push_back(x);
    }
    dfs(1);
    
    for (int i = 2; i <= N; i++) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}