백준 9489 사촌 Java

sovled.ac = 골드4 

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

9489번: 사촌

 

---

1. 접근

 

간선 정보를 어떻게 받을까 고민을 많이 했던 문제다...

 

사이클 되는 그래프의 경우는 일반적인 간선 입력처럼 받으면 되지만 트리 문제의 경우는 그냥 냅다 특정 노드의 부모는 누구인가? 를 저장하여 찾아가는 게 제일 간단한 것 같다.

 

입력에서 각 노드의 부모만 잘 입력받았다면 이제 찾아야 할 것은 딱 하나다.

 

예제 입력 1번을 예시로 위 조건을 그림으로 표현하면 다음과 같다.

즉, 두 노드의 부모는 다르지만 두 부모가 형제다 라는 것은 두 노드의 부모는 다르지만 부모의 부모가 같다!라고도 볼 수 있다.

 

그래서 예제 입력 1번은 찾고자 하는 15번 노드를 제외한 8, 9, 30, 31, 32 총 다섯 개가 답이 된다.

---

2. 풀이

 

변수 세팅

static int N, K, kIdx;
static int[] A, parent;
public static void main(String[] args) throws IOException {
    while (true) {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        // 두 값의 입력이 0이라면 테스트를 종료한다.
        if (N == 0 && K == 0) break;
        A = new int[N + 1];
        parent = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            if (A[i] == K) kIdx = i;
        }
        solution();
    }
}

 

사촌 찾기

static void solution() {
    int answer = 0;
    parent[0] = -1; // 루트 바로 아래자식에서 찾을 경우 카운트 방지
    parent[1] = 0; // 루트 노드의 부모는 없다.

    int idx = 1; // 부모 노드 인덱스
    for (int i = 2; i <= N; i++) {
        parent[i] = idx;
        // 연속된 수열이 아니라면 부모 노드 인덱스를 증가시킨다.
        if (i < N && A[i] + 1 != A[i + 1]) idx++;
    }
    for (int i = 1; i <= N; i++) {
        // 두 노드의 부모는 다르지만, 두 부모가 형제일 때
        // => 부모의 부모는 같으나 부모는 다를경우
        if (parent[parent[i]] == parent[parent[kIdx]] && parent[i] != parent[kIdx]) answer++;
    }
    System.out.println(answer);
}

 

---

3. 전체 코드