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

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

25511번: 값이 k인 트리 노드의 깊이

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K;
int arr[100001];
int parent[100001];

int dfs(int n, int cnt)
{
    if(n==0) return cnt; //루트 도달
    return dfs(parent[n], cnt+1); //루트찾기
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K;
    for(int i=0; i<N-1; i++)
    {
        int p, c;
        cin >> p >> c;
        parent[c]=p; 
    }
    int target = 0; //목표 정점 저장용
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        if(arr[i]==K) target=i;
    }
    cout << dfs(target, 0);
}

목표 정점에 대해 따로 저장을 해두고, 해당 값을 기준으로 부모를 계속해서 찾아나가면 된다.

부모를 찾아나갈때마다 깊이를 1 증가시켜주고, 부모의 값이 루트인 0을 만나면 종료시켜주면 된다.

 

목표 정점을 따로 저장했어야 했는데 단순히 arr[K]값을 나타내는 건줄알고 이를 토대로 했다가 여러번 틀렸다..

 

<예제>
8 5
0 1
0 2
1 3
1 4
2 5
2 6
6 7
0 1 2 3 4 5 6 7

target : 5
parent[5] = 2, cnt + 1(1)
parnet[2] = 0, cnt + 1(2)
깊이 : 2