[백준]BOJ 1068 트리(DFS/반례)

 

예시

 

[어려웠던 점]

 

처음에는 '전체 리프 노드 개수 - 지우려는 노드를 루트 노드로 했을 때 리프 노드 개수'를 진행하였다.

그러면, 다음 예시 같은 경우에는 0을 루트 노드로 하면 리프 노드 3개, 1을 루트 노드로 하면 리프 노드 2개이므로, 3 - 2 = 1이므로 답 1을 구할 수 있었다.

 

 

그런데, 이와 같은 경우는 다음과 같은 반례를 도출한다.

 

다음은 노드를 지우고 나면 루트 노드가 하나 남는 상황이다. 그렇다면 답은 1이 나와야 한다. 이와 같은 경우에서 나는 내가 기존에 생각했던 코드의 문제점을 찾아낼 수 있었다.

 

2
-1 0
1

 

 

그래서, 이 코드는 백준에서 70%~80%대에서 틀렸다....

 

 

 

---

 

[문제 해결 과정]

문제 해결 과정은 다음과 같다.

 

1. 연결 리스트에서 지우려고 하는 노드 번호와 일치하는 노드를 지운다.

2. 리프 노드의 개수를 구한다.

 

 

특히, 리프 노드의 경우 자식의 개수가 0을 의미한다. 이 의미는 DFS로 탐색할 때 리프 노드는 더 이상 탐색할 연결 노드가 없다는 의미이다. => size가 0이다.

 

 

 

---

 

[코드 구현]

public class Main_1068 {
	private static LinkedList<LinkedList<Integer>> tree;
	private static int N;
	private static int result;

	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		result = 0;
		int removeNode = 0;
		int rootIdx = 0;
		
		tree = new LinkedList<LinkedList<Integer>>();
		
		for (int i = 0; i < N; i++) {
			tree.add(new LinkedList<Integer>());
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int data = Integer.parseInt(st.nextToken());
			if(data == -1) {
				rootIdx = i;
				continue;
			}
			tree.get(data).add(i);
		}
		
		
		removeNode = Integer.parseInt(br.readLine());
	
		
		if(removeNode != rootIdx) {
			remove(removeNode);
			getCnt(rootIdx);
		}
		
		
		System.out.println(result);		
		
		
	}

	static void remove(int root) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < tree.get(i).size(); j++) {
				if(tree.get(i).get(j) == root) {//노드를 지움
					tree.get(i).remove(tree.get(i).get(j));
				}
			}
		}
	}
	
	static void getCnt(int now) {
		int size = tree.get(now).size();
		if(size == 0) {//size가 0인 경우는 leaf node이다.
			result++;
			return;
		}
		
		for (int i = 0; i < size; i++) {
			getCnt(tree.get(now).get(i));
		}
	}
	
}