[알고리즘 문제 풀기] 값이 k인 트리 노드의 깊이(25511)

1. 문제 풀이 아이디어

• 각 노드의 부모 정보를 저장하고, 특정 노드의 깊이를 구하기 위해 해당 노드에서 루트(0번 노드)까지 부모를 따라가며 깊이를 계산하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[] input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int n = input[0];
    int k = input[1];
    int[] p = new int[n];
    for (int i = 1; i < n; i++)
    {
        input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
        p[input[1]] = input[0];
    }
    input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int s = 0;
    for (int i = 0; i < n; i++)
    {
        if (k != input[i]) continue;
        s = i;
        break;
    }
    int depth = 0;
    while (s != 0)
    {
        s = p[s];
        depth++;
    }
    sw.WriteLine(depth);
}

3. 정리

• 다음 n-1개의 줄에서 각 노드의 부모 관계를 입력받아 p[자식] = 부모 형식으로 저장한다.

• 마지막 줄에서는 노드 번호들을 순서대로 입력받고, 이 중 k가 몇 번째 인덱스에 있는지를 찾아 해당 인덱스를 s에 저장한다.

• s를 루트(0번 노드)까지 부모 배열을 따라가며 거친 단계 수를 depth로 계산한다.

• 최종적으로 depth를 출력하여 해당 노드의 트리에서의 깊이를 구해 문제를 해결한다.