[BaekJoon] 1068 트리

1.  문제 링크

https://www.acmicpc.net/problem/1068

2.  문제

요약

• 트리가 주어졌을 때, 노드 하나를 지우는데 지우고 난 후에 남은 트리에서 리프 노드의 개수를 구하는 문제입니다.
• 노드를 지우면 그 노드 및 그 노드의 모든 자손이 트리에서 제거됩니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 트리의 노드의 개수 N이 주어지고 두 번째 줄에는 0번 노드부터 N - 1번 노드까지 각 노드의 부모가 주어지며 세 번째 줄에는 지울 노드의 번호가 주어집니다.
  • 만약 부모가 없다면 -1이 주어집니다.
• 출력: 첫 번째 줄에 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static ArrayList<Integer>[] parents;
	static int num;
	public void remove(int node) {
		if(parents[node].size() > 0) {
			int s = parents[node].size();
			while(s > 0) {
				int child = parents[node].get(--s);
				remove(child);
			}
		}
		for(int i = 0; i < num; i++) {
			if(parents[i].contains(node)) {
				for(int j = 0; j < parents[i].size(); j++) {
					if(parents[i].get(j) == node) {
						parents[i].remove(j);
					}
				}
			}
		}
	}
	
	public int findNumOfLeaf(int node) {
		Queue<Integer> q = new LinkedList<>();
		q.add(node);
		int count = 0;
		while(!q.isEmpty()) {
			int pos = q.poll();
			if(parents[pos].size() == 0) {
				count++;
				continue;
			}
			for(int next:parents[pos]) {
				q.add(next);
			}
		}
		return count;
	}
	
	public int getLeafNodeNum(int root, int del) {
		remove(del);
		if(del == root) {
			return 0;
		} else {
			return findNumOfLeaf(root);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		num = Integer.parseInt(br.readLine());
		parents = new ArrayList[num];
		for(int i = 0; i < num; i++) {
			parents[i] = new ArrayList<Integer>();
		}
		int root = -1;
		String[] input = br.readLine().split(" ");
		for(int i = 0; i < parents.length; i++) {
			if(Integer.parseInt(input[i]) == -1) {
				root = i;
				continue;
			}
			parents[Integer.parseInt(input[i])].add(i);
		}
		int del = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getLeafNodeNum(root, del) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS 및 BFS를 이용하여 해결할 수 있습니다.
• 하나의 노드를 삭제할 때, 해당 노드의 자손 노드들 모두 삭제해줘야하므로 DFS를 통하여 제거해줘야합니다.
• 자식노드가 없는 리프노드인 경우까지 재귀함수를 호출하고 리프노드인 경우 재귀함수 호출을 멈추고 삭제할 노드와 해당 노드의 자손 노드들을 모두 삭제합니다.

public void remove(int node) {
	if(parents[node].size() > 0) {
		int s = parents[node].size();
		while(s > 0) {
			int child = parents[node].get(--s);
			remove(child);
		}
	}
	for(int i = 0; i < num; i++) {
		if(parents[i].contains(node)) {
			for(int j = 0; j < parents[i].size(); j++) {
				if(parents[i].get(j) == node) {
					parents[i].remove(j);
				}
			}
		}
	}
}

• DFS를 통해 삭제할 노드 및 해당 노드의 자손 노드들을 모두 삭제한 후, 남은 트리의 리프 노드 개수를 구해야 하는데 이는 BFS를 이용하여 구할 수 있습니다.
• 루트 노드부터 시작하여 같은 level에 있는 형제 노드들, 이후에 아래 level에 있는 형제 노드들 순서로 탐색하면서 각 노드를 조회해 리프 노드를 찾아 개수를 세줍니다.

public int findNumOfLeaf(int node) {
	Queue<Integer> q = new LinkedList<>();
	q.add(node);
	int count = 0;
	while(!q.isEmpty()) {
		int pos = q.poll();
		if(parents[pos].size() == 0) {
			count++;
			continue;
		}
		for(int next:parents[pos]) {
			q.add(next);
		}
	}
	return count;
}

1. 각 노드를 부모로 하는 노드들을 저장하기 위해 노드의 개수에 해당하는 ArrayList 배열인 parents를 생성하고 해당 위치에 노드들을 설정합니다. 이 때, 부모가 -1인 노드는 루트 노드로서 root라는 변수에 설정합니다.
2. 삭제하고자 하는 노드 및 해당 노드의 자손 노드들 모두 삭제합니다.
   1. 삭제하고자 하는 노드를 부모로 하는 노드들의 개수가 0이 아니라면 해당 노드들에 대해 재귀함수를 호출합니다.
   2. 만약 삭제하고자 하는 노드를 부모로 하는 노드들의 개수가 0이라면 해당 노드를 트리에서 삭제합니다.
   3. 위 2가지 방법을 이용하여 재귀함수 호출을 통해 리프 노드까지 탐색한 후, 리프 노드부터 삭제하고자 하는 노드까지 트리에서 삭제합니다.
3. 만약 삭제하고자 하는 노드가 루트 노드라면 0을 출력합니다.
4. 만약 삭제하고자 하는 노드가 루트 노드가 아니라면 루트 노드부터 BFS를 통해 탐색하여 리프 노드의 개수를 찾습니다.
   1. 탐색하고자 하는 노드들을 저장하기 위한 Queue 하나를 생성하고 루트 노드를 Queue에 저장합니다. 또한 리프 노드의 개수를 나타내는 변수 count를 생성하고 0으로 초기화합니다.
   2. Queue가 빈 상태가 되기 전까지 반복문을 돌면서 리프 노드의 개수를 찾습니다.
      1. Queue에서 넣은 순서대로 노드 하나를 뽑아냅니다.
      2. 만약 해당 노드를 부모로 하는 노드가 없다면 해당 노드가 리프 노드이므로 리프 노드의 개수를 1 증가시킵니다.
      3. 만약 해당 노드를 부모로 하는 노드가 있다면 해당 노드들을 Queue에 넣습니다.
   3. 반복문이 끝났을 때의 변수 count 값이 리프 노드의 개수가 됩니다.