[BOJ] 9489 - 사촌

문제 링크

9489-사촌

문제 설명

입력

• 노드의 갯수 n
• 사촌을 구해야하는 노드의 수 k
  (각 테스트케이스별로) -> n,k가 모두 0이면 종료

출력

• k의 사촌의 수

문제 풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        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) return;
            int target = 0;
            int[] arr = new int[n + 1];
            int[] parent = new int[n + 1];
            int idx = -1;
            parent[0] = -1;
            arr[0] = -1;
            st = new StringTokenizer(br.readLine());

            for (int i = 1; i <= n; 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 result = 0;

            for (int i = 1; i <= n; i++) {
                if (parent[i] != parent[target] && parent[parent[i]] == parent[parent[target]]) {
                    result++;
                }
            }
            System.out.println(result);

        }
    }
}