[JAVA] 백준 1068 : 트리

문제

1068번: 트리

 

해결 방법

인접리스트를 활용해서 트리를 구현한 다음

리프노드를 체크해서 개수를 출력하였다.

 

리프노드(Leaf Node)란?

자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드) 라고 한다.

출처 : ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
	static ArrayList<Integer> list[];
	static boolean visit[];
	static int leafCnt = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		list = new ArrayList[N];
		visit = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<>();
		}
		
		int root = 0;
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			int temp = Integer.parseInt(st.nextToken());
			if (temp == -1) { // -1 일 경우는 루트노드.
				root = i;
			} else {
				list[i].add(temp); // 양방향으로 인접리스트를 추가한다.
				list[temp].add(i);
			}
		}
		
		int delNode = Integer.parseInt(br.readLine());
		if (delNode == root) { // 루트노드를 삭제하면 트리가 사라지기 때문에 0을 출력.
			System.out.println(0);
			return;
		}
		visit[delNode] = true; // 지울 노드는 이미 방문했다고 입력함으로써 처리.
		
		dfs(root);
		System.out.println(leafCnt);
	}
	
	static void dfs(int root) {
		boolean isLeaf = true; // 리프노드인지 아닌지 확인용.
		visit[root] = true;
		
		for (int i = 0; i < list[root].size(); i++) {
			if (visit[list[root].get(i)] == false) {
				isLeaf = false; // 추가로 탐색해야하는 부분이 있으면 리프노드가 아님.
				dfs(list[root].get(i));
			}
		}
		
		if (isLeaf) { // 반복문이 끝나고 추가 탐색이 일어나지 않았으면 리프노드.
			leafCnt++;
		}
	}
}