25511 c++ - 값이 k인 트리 노드의 깊이

문제 제목이나 분류를 보면 트리로 되어있지만, 굳이 트리로 풀지 않아도 됩니다.

결국 깊이를 찾는 문제이므로, 부모의 정점을 기억하여 0으로 고정되어있는 root를 찾아서 거슬러 올라가면 찾을 수 있습니다.

기본적인 그래프 문제. 트리로 풀려다가 이진 트리가 아니면 부모의 인덱스로 찾기가 어려워질것 같아서 부모만 잡아서 풀었습니다.
자료구조를 편협하게 정해서 "무조건 이걸로 풀어야해"하면서 문제에 덤비게 되면 눈 뜬 장님이 되어버리는 경우가 생기는 것 같습니다.
이런 문제도 그렇고 bfs도 그렇고.. 그래서 좀 시각을 넓게 보고 이게 '확실한가 ?', '이게 최적인가 ?' 하는 의심을 계속해서 해보고 더이상 의심이 들지 않을때 문제를 풀어내는 습관을 들이는 중입니다.

뭐 많이 의심해도 그게 잘못된거면, 아직은 실력이 부족한가 보다. 더 열심히 해야 겠다. 하면서 정진하고 있습니다. 😂

 

 

 

c++ 정답 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;

  vector<int> parent(n, -1);
  vector<int> values(n);
  int root = 0;

  for (int i = 0; i < n - 1; i++) {
    int p, c;
    cin >> p >> c;
    parent[c] = p;
  }

  for (int i = 0; i < n; i++) {
    cin >> values[i];
  }

  int target_node = -1;
  for (int i = 0; i < n; i++) {
    if (values[i] == k) {
      target_node = i;
      break;
    }
  }

  int depth = 0;
  while (target_node != root) {
    target_node = parent[target_node];
    depth++;
  }

  cout << depth;

  return 0;
}