[BOJ] 백준 9489번 사촌 (Java)

#9489 사촌

난이도 : 골드 4

유형 : 트리

9489번: 사촌

▸ 문제

증가하는 정수 수열을 이용해서 트리를 만드는 방법은 다음과 같다.

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

예를 들어, 수열 1 3 4 5 8 9 15 30 31 32를 위의 규칙을 이용해 트리를 만들면 아래 그림과 같이 된다.

 

두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다.

수열 특정 노드 번호 k가 주어졌을 때, k의 사촌의 수를 구하는 프로그램을 작성하시오.

▸ 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄에는 총 n개의 수가 주어지며, 모든 수는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 입력으로 주어지는 수열은 항상 증가한다. k는 항상 수열에 포함되는 수이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

▸ 출력

각 테스트 케이스 마다, k의 사촌의 수를 출력한다.

 

문제 풀이  

노드번호가 2이상 차이나는 부분으로 집합을 구분하여 차례대로 부모노드를 구해주면 된다. 그 다음 k와 같은 부모가 아니고 k의 2번째 부모와 일치하는 노드들의 수를 출력해주면 된다. 

 

설계

1. 주어진 노드 번호를 arr배열에 저장한다. parent 배열에는 i노드의 부모노드를 저장한다.
   1. 만약 이전노드와의 차이가 1보다 크게 난다면 다른 집합에 속해있는 것이므로 idx를 증가시킨다.
   2. if(arr[i] != arr[i-1]+1) idx++;
   3. parent[i] = idx;
   4. k와 일치하는 노드 번호를 taget에 저장한다.
2. 그렇게 구한 parent 데이터로 target과 같은 부모가 아니고 두 번째 부모가 일치하는 노드의 수를 찾아서 출력한다.
   1. if(parent[i] != parent[target] && parent[parent[i]] == parent[parent[target]]) answer++;

 

풀이 코드 

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) break;
			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 answer = 0;
			for(int i=1; i<=n; i++) {
				if(parent[i] != parent[target] && parent[parent[i]] == parent[parent[target]]) {
					answer++;
				}
			}
			sb.append(answer+"\n");
		}
		System.out.println(sb.toString());
	}
}