백준 9489 사촌 Java

백준 9489 사촌 Java

728x90

sovled.ac = 골드4

https://www.acmicpc.net/problem/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. 전체 코드

728x90

from http://dhbang.tistory.com/38 by ccl(A) rewrite - 2021-12-22 17:27:03