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

 

 

 

---

⬛ 문제

 

 

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

1068번: 트리

 

 

 

---

⬛ 풀이

 

얼핏보면 주어진 입력대로 트리를 구성하고, DFS를 통해 리프노드 갯수를 구하는 단순한 문제이다. 

 

하지만 문제 어디에도 입력 트리가 이진 트리라는 말도, 입력 값이 오름차순이라는 말도, 루트가 하나라는 전제도 없다. (물론 이번 문제는 루트는 하나이다.)

 

초반에 입력이 오름차순일 것이라고 가정하여 IndexOutOfBounds를 줄기차게 먹었다;;

 

프로그램 전체 로직은 다음과 같다. 

1. 노드 갯수만큼 List<Node>에 Node 객체를 추가한다.

2. 입력 값을 확인하여 Node들의 부모 - 자식 관계를 매핑한다. 이때 부모가 -1이라면 root로 지정한다.

3. 삭제할 노드 번호를 List<Node>에서 제거한다. 

4. root부터 DFS를 하여 그 자식들 중 List<Node>에 포함된 자식들만 DFS를 호출한다. 

5. 한번도 DFS를 호출하지 못하면 leafNode 카운트를 1 증가한다.

 

예시 입력: 5 2 6 0 0 -1 5 5 6

 

1. 9개의 Node 객체 추가

 

 

2. 부모 - 자식 관계 매핑

 

 

3. List에서 노드 제거(객체 자체의 삭제는 아님)

 

 

4. 루트(5) 부터 DFS 탐색, 만약 DFS 호출할 자식이 없다면 LeafNode 카운트 1 증가

 

 

 

---

⬛ 코드

 

package d0814;

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

/*
백준 1068 트리

	Node 클래스: <Node> 리스트인 nodeList를 가지고 자식 노드를 저장
	tree: <Node>리스트임. 전체 트리를 구성하는 노드들을 저장하고 각 인덱스는 노드 번호를 의미한다.
			
 */

public class BJ_1068 {

	/****************** Class ******************/
	static class Node {
		ArrayList<Node> nodeList = new ArrayList<>();  
	}
	/****************** Class End ******************/

	
	
	static int leafNode = 0;
	static ArrayList<Node> tree = new ArrayList<>();
	
	/****************** Main ******************/
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		// tree에 전체 노드 갯수만큼 Node 객체를 생성하여 추가
		for (int i = 0; i < n; i++) {
			Node newNode = new Node();
			tree.add(newNode);
		}

		Node root = null;
		StringTokenizer st = new StringTokenizer(br.readLine());

		// tree에서 Node별로 부모-자식 관계 매핑해주는 작업
		for (int i = 0; i < n; i++) {
			
			int parentIdx = Integer.parseInt(st.nextToken()); // 입력값, 즉 부모 Node의 인덱스 값
			Node curNode = tree.get(i); // tree에서 현재 Node 로드

			// 부모 인덱스가 -1이면 root
			if (parentIdx == -1) {
				root = curNode;
				continue;
			}

			// 부모가 있으면 tree에서 부모 Node를 불러오고 부모의 nodeList에 현재 Node를 저장
			Node parentNode = tree.get(parentIdx);
			parentNode.nodeList.add(curNode);
		}

		// Node 하나 삭제
		int deleteNodeIdx = Integer.parseInt(br.readLine());
		tree.remove(tree.get(deleteNodeIdx));

		// root부터 dfs
		if (tree.contains(root)) // 루트가 삭제되었을 수도 있으므로 체크
			dfs(root);
			
		System.out.println(leafNode);
	}
	/****************** Main End ******************/

	
	
	/****************** Method ******************/

//	dfs: 자식으로 dfs를 호출하지 못하면 leafNode++
	static void dfs(Node node) {
		boolean dfsCall = false;

		for (Node n : node.nodeList)
			// 삭제된 노드인지 체크
			if (tree.contains(n)) {
				dfsCall = true;
				dfs(n);
			}

		if (!dfsCall)
			leafNode++;
	}
	/****************** Method End ******************/
}