[백준] 2233 사과나무 자바

문제

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

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

0 0 0 1 0 1 1 0 1 1

a	b	c		d			e
			c		d	b		e	a

이진수의 각 숫자들은 그 숫자가 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 번째임을 나타낸다.

---

테스트 케이스

 

입력 1

12
000011001111
4 8

출력 1

2 11

 

입력 2

5
0001011011
4 5

출력 2

2 7

 

입력 3

1
01
1 1

출력 3

1 2

---

접근

주어진 2진수를 이용해서 트리로 바꾼후 LCA를 사용해주니 문제가 해결되었습니다.

---

코드

import java.util.*;
import java.io.*;
class TreeNode{
	int val;
//	TreeNode left;
//	TreeNode right;
	List<TreeNode> children = new ArrayList<>();
	TreeNode prev;
	public TreeNode(int val) {
		this.val = val;
	}
}
public class Main {
	static TreeNode cur;
	static TreeNode res;
	static public boolean recurTree(TreeNode cur, TreeNode p ,TreeNode q) {
		if(cur == null) return false;
		int childSize = cur.children.size();
		int num = 0;
		for(int i=0; i<childSize; i++) {
			num += recurTree(cur.children.get(i), p, q)? 1:0;
		}
		int mid = (cur == p || cur == q)?1:0;
		if(num+mid >= 2) {
			res = cur;
		}
		return (num+mid > 0);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		TreeNode p = null;
		TreeNode q = null;
		TreeNode root = new TreeNode(1);
		TreeNode arr[] = new TreeNode[s.length()+1];
		cur = root;
		res = root;
		
		int index = 2;
		arr[1] = root;
		
		for(int i=1; i<s.length(); i++) {
			if(s.charAt(i) == '0') {
				cur.children.add(new TreeNode(index++));
				arr[i+1] = cur.children.get(cur.children.size()-1);
				arr[i+1].prev = cur;
				cur = arr[i+1];
			}
			else {
				arr[i+1] = cur;
				cur = cur.prev;
			}
		}
		StringBuilder sb = new StringBuilder();
		p = arr[x];
		q = arr[y];
		if(p==q) res = p;
		else recurTree(root, p, q);
		for(int i=1; i<arr.length; i++) {
			if(arr[i].val == res.val ) {
				sb.append(i+" ");
			}
		}
		System.out.println(sb.toString());
		br.close();
	}
}

---

주의

저 같은 경우 자식사과가 무조건 2개만 올줄 알고, 풀었는데 그러니까 계속 9%에서 틀렸다고 떴습니다....

(시간 매우 많이 씀....)

알고보니 2개이상 올 수 있더라구요, 그 부분을 해결하니 문제가 풀렸습니다.