백준 / 11725 / 트리의 부모 찾기 / C++

문제 링크 : https://www.acmicpc.net/problem/11725

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> tree;
vector<int> dist;

void dfs(int curidx, int curdist)
{
    if(dist[curidx] < curdist)
    {
        return;
    }
    int size = tree[curidx].size();
    dist[curidx] = curdist;
    for(int i = 0; i < size; i++)
    {
        dfs(tree[curidx][i],curdist + 1);
    }
}

void printans(int idx)
{
    int minval = INT_MAX;
    int paridx;
    int size = tree[idx].size();
    for(int i = 0; i < size; i++)
    {
        if(dist[tree[idx][i]] < minval)
        {
            minval = dist[tree[idx][i]];
            paridx = tree[idx][i];
        }
    }
    cout << paridx << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    tree.resize(n + 1,vector<int>());
    dist.resize(n + 1, INT_MAX);
    for(int i = 0; i < n - 1; i++)
    {
        int a,b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    dfs(1,0);
    for(int i = 2; i <= n; i++)
    {
        printans(i);
    }
    return 0;
}

각 노드의 부모 노드를 출력하는 문제이다. 생각해본 아이디어는 인접리스트로 트리를 구현한 다음 노드 1에 대해 DFS를 해서 1에서의 거리를 dist 배열에 저장하고, 각 노드에 대해 인접해 있는 노드들 중 dist 값이 더 작은 노드를 출력하는 방식이다.
구현도 간단했고 트리 문제를 이전에 몇개 풀어 봐서 수월하게 푼 것 같다.

클래스 4에서 아무 문제나 뽑아서 푸는데 왜인지 계속 그래프랑 트리 문제만 걸리는 것 같다...