[BOJ] 백준 2233번 사과나무 (Java)

#2233 사과나무

난이도 : 골드 1

유형 : 트리 / LCA

2233번: 사과나무

▸ 문제

사과나무는 나무(tree)의 일종으로, 각각의 정점에 정확히 한 개의 사과가 있고, 모든 내부 정점(자식이 있는 정점)이 최소 두 개의 자식을 갖는 나무이다. 예를 들면 아래의 그림은 사과나무의 예이다. 나무같이 보이기 위해서 그림은 루트를 아래에 그린다.

이러한 사과나무에 서식하는 벌레를 생각해 보자. 이 벌레는 이 사과나무의 루트에서 DFS 순서로 탐색을 하게 된다. 자식이 여러 개인 경우에는 (뒤집혀진 그림에서) 왼쪽을 먼저 방문하게 된다. 이러한 탐색을 하면서, 새로운 노드를 방문할 때 0을, 모든 자식 노드를 방문하고 리턴할 때 1을 나열하면 하나의 이진 수열이 된다. 위의 그림으로 이진 수열을 만들면 다음과 같다.

 

 

이진수의 각 숫자들은 그 숫자가 0이든 1이든 하나의 정점에 대응되게 된다. 즉 0의 경우에는 새로 방문되는 정점에 대응되고, 1의 경우에는 리턴하기 전에 있었던 정점에 대응된다. 위의 표에서는 각 숫자에 대응되는 정점도 표시하였다.

이러한 사과나무에서 썩은 사과가 발견된 경우에는 가지를 잘라 내어야 한다. 만약 우리가 어떤 정점을 제거하면, 그 정점과 그 자손 정점들이 모두 제거되게 된다. 위의 예에서 b를 제거하면 b, c, d가 모두 제거되게 된다.

만약 한 개의 사과가 썩은 경우라면 그 사과를 제거하면 되지만, 두 개의 사과가 썩은 경우라면 문제가 복잡해진다. 사과나무의 성질을 유지하기 위해서, 우리는 오직 한 개의 사과만 제거할 수 있다. 이 경우 루트를 제거하면 되지만, 루트를 제거하게 되면 멀쩡한 사과들을 많이 잃게 된다(제거되는 것은 잃는 것). 따라서 우리는 한 개의 사과를 제거하되, 이를 통해 두 개(이하)의 썩은 사과를 함께 제거하고, 그러면서도 가장 적은 개수의 멀쩡한 사과를 잃도록 잘라야 한다. 위의 예에서 c, d의 사과가 썩은 경우에는 b를 제거하면 된다.

사과나무에 대한 정보가 주어졌을 때, 제거해야 하는 사과를 알아내는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리의 이진수에서 X번째의 숫자에 대응되는 정점과, Y번째 숫자에 대응되는 정점에 있는 사과가 썩었다는 의미이다. 이때 두 정점이 서로 같을 수도 있다.

▸ 출력

첫째 줄에 제거해야 할 사과를 나타내는 두 정수 i, j를 출력한다. 제거해야 할 사과를 Z라고 했을 때, 이는 Z를 방문할 때의 0의 위치와 Z에서 리턴될 때의 1의 위치가 이진수에서 각각 i, j 번째임을 나타낸다.

 

문제 풀이  

주어진 이진수열의 특징을 먼저 살펴보자. 0은 노드가 있는 곳이고, 1은 노드가 나오는 곳이다. 따라서 (01)의 한 묶음이 한 노드를 나타낸다고 보면 된다. 처음에는 DFS와 스택을 이용하여 풀이를 하려다가 변수가 너무 많아 힌트를 보고 LCA로 방향을 틀었다.

 

초기값 설정이 해당 구현의 대부분을 차지한다. 주어진 예제 초기값 설정값은 다음과 같다.

• nodeIdx: 이진배열 위치에 각 노드의 번호를 저장한다.

 

	0	0	0	1	0	1	1	0	1	1
nodeIdx	1	2	3	3	4	4	2	5	5	1

 

• detph: 노드의 depth를 저장한다.
• parent[idx][h]: idx의 2^h 부모 노드를 저장한다.

 

	1	2	3	4	5
depth	1	2	3	3	2
2^0번째 parent	0	1	2	2	1
2^1번째 parent	0	0	1	1	0

 

그 다음 LCA를 찾아 해당 노드의 0과 1의 인덱스를 출력해주면 된다.(2, 7)

 

	0	0	0	1	0	1	1	0	1	1
nodeIdx	1	2	3	3	4	4	2	5	5	1

 

설계

1. 주어진 이진수열을 가지고 LCA 노드의 초기값 설정을 한다.
   1. parent, depth, nodeIdx
2. s, e에 해당하는 노드 번호를 nodeIdx를 통해 받고 해당 노드의 LCA를 구한다 lca(nodeIdx[s], nodeIdx[e])
3. 2번에서 구한 lca 노드 번호를 가지고 이진수열에 위치한 0과 1의 위치를 출력한다.
   1. if(nodeIdx[i]==lcaIdx) print(i);

 

풀이 코드 

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

public class Main {

	static int[][] parent;
	static int[] depth, nodeIdx;
	static int n, size, s, e, i, j;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		char[] data = br.readLine().toCharArray();
		size = (int)Math.ceil(Math.log(n)/Math.log(2))+1;
		parent = new int[n+1][size];
		depth = new int[n+1];
		nodeIdx = new int[2*n+1];
		int idx = 1;
		int cur = 0;
		for(int i=1; i<=data.length; i++) {
			if(data[i-1]-'0' == 0) {
				parent[idx][0] = cur;
				depth[idx] = depth[cur] +1;
				nodeIdx[i] = idx; 
				cur = idx++;
			}else {
				nodeIdx[i] = cur;
				cur = parent[cur][0];
			}
			
		}
		fillParents();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		s = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		int lcaIdx = lca(nodeIdx[s], nodeIdx[e]);
		
		for(int i=1; i<n*2+1; i++) {
			if(nodeIdx[i]==lcaIdx) {
				System.out.print(i+" ");
			}
		}
	}
	
	static void fillParents() {
		for(int i=1; i<size; i++) {
			for(int j=1; j<n+1; j++) {
				parent[j][i] = parent[parent[j][i-1]][i - 1];
			}
		}
	}
	
	static int lca(int x, int y) {
		if(depth[x] > depth[y]) { // xh < yh 
			int tmp = x;
			x = y;
			y = tmp;
		}
        
		// 키 맞추기 
		for(int i= size-1; i>=0; i--) {
			if(Math.pow(2, i) <= depth[y] - depth[x]){
				y = parent[y][i];
			}
		}
		
		if(x == y) return x;
		
		for(int i= size-1; i>=0; i--) {
			if(parent[x][i]!=parent[y][i]) {
				x = parent[x][i];
				y = parent[y][i];
			}
		}
		return parent[x][0];
	}
}