[백준, Java] 1068번 : 트리

🔗 문제 링크

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

😮 문제 해결 방법

Map을 이용해 구현에 필요한 트리를 만들어 준 후 DFS를 이용해 루트 노드부터 탐색한다.

1. Map에서 현재 노드에 해당하는 리스트가 없는 경우는 단말 노드이기 때문에 단말 노드 카운트를 증가시킨다.
2. 현재 노드가 삭제할 노드인 경우는 다음 노드들은 모두 삭제 되므로 그대로 return한다.
3. 만약 현재 노드에서 연결된 자식 노드가 삭제되는 노드이면서 단말 노드인 경우는 삭제 후 현재 노드가 단말노드가 되기 때문에 단말 노드 카운트를 증가시킨다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_1068_트리 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Map<Integer, List<Integer>> tree = new HashMap<>();
        // 트리 초기화
        for (int node = 0; node < N; node++) {
            tree.put(node, new LinkedList<>());
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int rootNode = 0;

        // 트리 연결
        for (int node = 0; node < N; node++) {
            int parent = Integer.parseInt(st.nextToken());
            if (parent != -1) {
                tree.get(parent).add(node);
            } else {
                rootNode = node;
            }
        }

        // 제거할 노드
        int removeNode = Integer.parseInt(br.readLine());
        leaf = 0;

        getLeafNode(rootNode, removeNode, tree);
        System.out.println(leaf);

        br.close();
    }

    private static int leaf;

    private static void getLeafNode(int start, int remove, Map<Integer, List<Integer>> tree) {
        // 삭제할 노드 도달 시 이후는 DFS 안함
        if (start == remove) {
            return;
        }

        // 연결된 노드가 없으면 리프노드
        if (tree.get(start).size() < 1) {
            leaf++;
            return;
        }

      // 연결된 노드 방문 처리 및 자식 노드 방문
        for (int next : tree.get(start)) {
			// 연결된 자식 노드가 삭제할 노드이고, 연결된 노드가 한개인 경우 -> 자식 노드가 단말 노드인 경우
            if(next == remove && tree.get(start).size() == 1) {
                leaf++;
            }
            getLeafNode(next, remove, tree);
        }
    }
}