[BOJ 9489] 사촌 (Java, 트리)

 

---

문제 링크 

https://www.acmicpc.net/problem/9489

9489번: 사촌

---

문제 풀이

- (중요) 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라 함 

- 입력 초기화할 때 이전 노드와 현 노드 차이가 1이 아닌 경우 부모 노드 인덱스(parentIdx)를 변경하여 PARENT 배열 정의

- PARENT 배열을 구한 후 선형 탐색 하여 O(N) 시간복잡도 가짐

 

TARGET 노드가 있을 때
TARGET 노드의 부모와 비교 대상 노드의 부모가 다르지만, 두 부모의 부모가 같다면 둘은 형제 노드라 할 수 있다

 

- 첫번째 정수가 트리의 루트 노드 

- 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타냄, 이 집합에 포함된 수의 첫번째 수는 항상 루트 노드 + 1보다 크다

- 그 다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 된다. 

- 집합은 수가 연속하지 않는 곳에서 구분된다 ( => 이전 노드와 현 노드의 값의 차이가 1이 아니면 부모 노드 인덱스(parentIdx) 증가)

 

출처 : 백준 9489번 사촌

 

실수*

입력 정보 초기화시 
Loop 바깥에서 Root 노드를 부모 노드 정보를 직접 초기화 할 경우 ArrayIndexOutOfBound 에러 발생

---

제출 코드

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

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

    static int N, K, TARGET_IDX;

    static int[] DATA, PARENT;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String input = "";
        while(true) {
            input = br.readLine();
            if("0 0".equals(input)) break;

            st = new StringTokenizer(input);
            N = Integer.parseInt(st.nextToken()); // 노드의 수
            K = Integer.parseInt(st.nextToken()); // 사촌의 수

            st = new StringTokenizer(br.readLine());
            DATA = new int[N + 1];
            PARENT = new int[N + 1];

            PARENT[0] = -1;

            int parentIdx = 0;
            for(int i = 1; i <= N; i++) {
                DATA[i] = Integer.parseInt(st.nextToken());
                if(DATA[i] == K) TARGET_IDX = i;
                if(i > 1 && DATA[i] - DATA[i - 1] != 1) parentIdx += 1;

                PARENT[i] = parentIdx;
            }

            pro();
        }
    }
    static void pro() {
        int cnt = 0;
        for(int i = 1; i <= N; i++) { // 부모 노드가 같지 않고, 부모 노드가 형제인 경우
            if(PARENT[i] != PARENT[TARGET_IDX] && PARENT[PARENT[i]] == PARENT[PARENT[TARGET_IDX]]) cnt += 1;
        }

        sb.append(cnt).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
    
}