[C++][백준 25511] 값이 k인 트리 노드의 깊이

문제

접근 방법

트리를 구성하고 트리에서 특정 값을 찾아내는 문제입니다.
출력하는 값은 특정 값이 속한 깊이이므로 탐색 과정에서 깊이를 기록해야 합니다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using pii = pair<int, int>;
int n, k;
vector<vector<int>> edges;
vector<int> vertexs;
queue<pii> q;

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;

    vertexs = vector<int>(n);
    edges = vector<vector<int>>(n, vector<int>());

    for (int i = 1, p, c; i < n; ++i)
    {
        cin >> p >> c;
        edges[p].push_back(c);
    }

    for (int &vertex : vertexs)
    {
        cin >> vertex;
    }
}

void solve()
{
    q.push({0, 0});

    while (!q.empty())
    {
        pii cur = q.front();
        q.pop();

        if (vertexs[cur.second] == k)
        {
            cout << cur.first;
            break;
        }

        for (int next : edges[cur.second])
        {
            q.push({cur.first + 1, next});
        }
    }
}

int main()
{
    input();
    solve();
    return 0;
}

풀이

트리를 탐색할 수 있는 DFS, BFS 모두 사용할 수 있습니다.
입력으로 트리를 구성해 준 뒤 문제 해결에서 탐색을 하여 k를 찾아내고 k가 속한 깊이를 출력합니다.
0 또한 k가 될 수 있다는 점을 고려하여 코드를 작성해 주면 됩니다.