[BOJ] 백준 1068번 트리 (Java)

#1068 트리

난이도 : 골드 5

유형 : 그래프 / BFS/ DFS

1068번: 트리

▸ 문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

 

▸ 입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

 

▸ 출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

 

 

문제 풀이 

트리 탐색 문제이다. 인접리스트배열을 사용하여 노드들의 정보를 저장해주고 삭제할 노드는 DFS탐색으로 모두 조회하여 노드를 제거해주고 BFS탐색으로 리프노드의 수를 구해주었다.

 

📚 조건

   ∙ 트리 노드의 개수 N (1 <= N <= 50)

   ∙ 0~N-1번 노드의 부모가 주어지는데 루트 노드의 부모는 -1로 주어진다.

 

1) DFS탐색으로 노드 삭제하기

단순히 해당 노드를 삭제하는 것이 아니라 그 노드의 자식노드의 자식노드의 자식노드... 이렇게 연결된 모든 노드를 삭제해주어야 하기 때문에 DFS탐색으로 재귀호출의 Stack방식을 활용하여 제거해줘야한다. 자식노드가 더 이상 없는 리프노드인 경우 재귀함수 호출을 그만하고 노드를 삭제해주면 된다. 

static void removeNode(int node) {
	// node의 자식 노드 탐색
	if(list[node].size()>0) {
		int size = list[node].size();
		while(size>0) {
			int child = list[node].get(--size);
			removeNode(child);
		}
	}
	// node의 자식 노드 모두 삭제 
	for(int i=0; i<n; i++) {
		if(list[i].contains(node)) {
			for(int j=0; j<list[i].size(); j++) {
				if(list[i].get(j) == node) {
					list[i].remove(j);
				}
			}
		}
	}
}

 

2) BFS탐색으로 리프노드 갯수 구하기

이 또한 간단하다. 자신이 코드에 노드를 어떤식으로 저장했느냐에 따라 구현방법은 다르겠지만 나는 인접리스트 배열로 저장해줬기 때문에 BFS와 LinkedList를 사용하여 각 노드를 조회해주며 리프노드를 간단하게 카운트해주었다. 그리고 단방향 트리 탐색이기 때문에 따로 방문노드 체크는 해주지 않아도 상관없다.

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

 

 

풀이 코드 

사실 이렇게말고 더 간단하게 DFS탐색을 하면서 구할 수 있지만 좀 더 문제의 본질에 맞추고자 직관적으로 두개의 메소드를 설계하여 풀이하였다. 그리고 삭제할 노드가 root인 경우에는 0으로 출력해주는 예외처리를 해줘야한다.

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

public class Main {
	
	static int n;
	static List<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		list = new ArrayList[n];
		for(int i=0; i<n; i++) {
			list[i] = new ArrayList<>();
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		int root = -1;
		for(int i=0; i<n; i++) {
			int num = Integer.parseInt(st.nextToken());
			if(num == -1) {
				root = i;
				continue;
			}
			list[num].add(i); 
		}
		
		int remove = Integer.parseInt(br.readLine());
		
		removeNode(remove);
		if(remove == root) {
			System.out.println(0);
		}else {
			System.out.println(findLeaf(root));
		}
	}
	static void removeNode(int node) {
		
		// 해당 노드 자식노드 모두 조회 
		if(list[node].size()>0) {
			int size = list[node].size();
			while(size>0) {
				int child = list[node].get(--size);
				removeNode(child);
			}
		}
		
		// 해당 노드 자식 노드 모두 삭제 
		for(int i=0; i<n; i++) {
			if(list[i].contains(node)) {
				for(int j=0; j<list[i].size(); j++) {
					if(list[i].get(j) == node) {
						list[i].remove(j);
					}
				}
			}
		}
	}
	
	static int findLeaf(int node) {
		Queue<Integer> q = new LinkedList<>();
		q.add(node);
		int cnt=0;
		
		while(!q.isEmpty()) {
			int pos = q.poll();
			if(list[pos].size()==0) { 
				cnt++; // 리프노드 count
				continue;
			}
			
			for(int next : list[pos]) {
				q.add(next);
			}
		}
		return cnt;
	}
	
}