BOJ : 9489 사촌

---

출처 : https://www.acmicpc.net/problem/9489
난이도 : 골드 4
풀이날짜 : 2022-12-19

---

---

풀이

아이디어

그림만 봐도 이것이 트리인 것을 알 수 있습니다.
용어를 정리 해보는 것으로 문제를 간단히 풀 수 있습니다.

부모의 자식들 중 자신을 제외한 것은 형제입니다.

사촌은 부모의 부모의 자식의 자식입니다.

하지만 형제는 사촌이 아닙니다.

즉 사촌은 부모의 부모의 자식의 자식이지만 나랑 부모가 다른 사람들이 됩니다.

이를 통해서 특정 노드의 부모를 찾는 방법과 특정 노드의 자식을 찾는 것으로 문제를 해결 할 수 있습니다.

자료 구조

트리이지만 간단히 부모인지만 알면 됩니다.
parent[] 배열에 부모를 가르키고 부모가 다르면서 부모의 부모가 같은 것을 세주면 됩니다.

입력

1. 첫 번째 정수는 트리의 루트 노드이다.
2. 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타낸다. 이 집합에 포함되는 수의 첫 번째 수는 항상 루트 노드+1보다 크다.
3. 그 다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 된다. 그러한 노드가 여러 가지 인 경우에는 가장 작은 수를 가지는 노드의 자식이 된다.
4. 집합은 수가 연속하지 않는 곳에서 구분된다.

이 조건들을 생각해서 입력을 처리하는 것이 중요합니다.

부모 인덱스를 정해주고 만약 입력이 연속하지 않으면 부모 인덱스를 올려주고 자식으로 받는 것으로 문제가 해결이 될 것 같습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class No9489 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		while(true) {
			st = new StringTokenizer(br.readLine());
			
			// n, k 입력 받기
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			if(n==0 && k==0) break;
			
			// 배열 입력 받기
			int[] arr = new int[n];
			// 부모 저장
			int[] parent = new int[n];
			// 맨 위의 노트는 -1
			parent[0] = -1;
			st = new StringTokenizer(br.readLine());
			
			// 찾고자 하는 k 위치
			int fidx = -1;
			
			// 배열 입력
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
				if(k==arr[i]) fidx = i;
			}
			
			// 배열의 크기가 1 초과일 경우!
			// 1번째는 0을 가르키고 있다.
			// 입력이 만약 1 2 3 이런 식으로 들어와도 1은 2와 3의 부모가 되어야 한다
			if(n > 1) {
				parent[1] = 0;
			}
			// 부모의 위치 (연속이 아니면 하나씩 이동)
			int pidx = 0;
			
			// 2번째부터 보기
			for(int i=2; i<n; i++) {
				if(arr[i-1] != arr[i] - 1)
					pidx++;
				parent[i] = pidx;
			}
			int count = 0;
			
			// 배열을 돌면서 부모가 다르면서 부모의 부모가 같은 것들을 세줍니다.
			for(int i=0; i<n; i++) {
				if(parent[i]==-1 || parent[parent[i]] == -1) continue;
				if(parent[i]!=parent[fidx] && parent[parent[i]] == parent[parent[fidx]]) count++;
			}
			// sb에 저장
			sb.append(count +"\n");
		}
		// sb 출력
		System.out.println(sb);
		br.close();
	}
}

---

결과

child를 따로 ArrayList로 만들어 주었으나 메모리 초과가 발생하였습니다. 굳이 Child를 볼 필요가 없다는 것을 알았습니다.

---

느낀점

많이 헤맸던 문제라 여러번 볼 것