[백준] 9489 사촌 - Java

 

 

 

트리를 저장할 때 항상 리스트 배열과 행렬을 사용해야 하는 건 아니다.

위의 두 방법 말고도 배열 2개를 통해 해당 노드의 부모와 해당 노드의 값을 저장할 수 있다.

 

트리를 저장하는 방법은 문제에 따라 유동적으로 바꿔서 사용하자.

 

(https://loosie.tistory.com/608 참고 블로그)

 

 

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            if(N == 0 && K == 0){
                break;
            }

            int[] arr = new int[N+1];
            int[] parent = new int[N+1];

            int idx = -1;
            int target = 0;

            parent[0] = -1;
            arr[0] = -1;

            st = new StringTokenizer(br.readLine());

            for(int i=1; i<N+1; i++){
                arr[i] = Integer.parseInt(st.nextToken());

                if(arr[i] == K){
                    target = i;    
                }

                if(arr[i] != arr[i - 1] + 1){
                    idx++;
                }

                parent[i] = idx;
            }

            int ans = 0;

            for(int i=1; i<N+1; i++){
                if(parent[i] != parent[target] && parent[parent[i]] == parent[parent[target]]){
                    ans++;
                }
            }

            sb.append(ans + "\n");

        }

        System.out.println(sb);


    }
    
}