[백준] 1068 트리 (JAVA)

문제링크:

1068번: 트리

 

문제:

 

 

입력:

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

 

출력:

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

 

문제이해:

트리에서 리프 노드는 자식이 없는 노드이고, 특정 노드를 삭제하면 그 노드와 모든 자손이 제거된다. 문제는 삭제 후 남은 트리에서 리프 노드가 몇 개인지를 세는 것이문제이다. 쉽게 예를 들어 이해해보자. 예제 입력 4는 다음과 같다.

즉 출력은 2가 되는 것이다.

 

구현 방향:

먼저 root 노드는 0번이 아닐 수 도 있고 2진트리가 아니기에 자식이 3명이 존재할 수 있다는 것을 인지해야한다.

 

트리에서 지우고 싶은 노드를 선택하면, 그 노드뿐만 아니라 모든 자식, 손자, 증손자까지 모두 삭제 표시를 한다. 이렇게 하면 삭제된 노드는 더 이상 트리에서 존재하지 않는다.

 

그다음, 트리의 처음부터 끝까지 남아 있는 모든 노드를 순차적으로 확인하면서, 다른 노드의 부모로 지정되어 있지 않은 노드를 찾는다. 이 노드들은 더 이상 자식이 없는 남은 리프 노드이다.

 

마지막으로, 이렇게 확인한 리프 노드를 하나씩 세어서 최종적으로 남은 리프 노드의 개수를 계산한다.

 

이를 그대로 코드로 구현하면 다음과 같다.

 

정답 코드:

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

public class Main {

    static int[] graph;       // 각 노드의 부모 인덱스 저장
    static boolean[] isNotLeaf;
    static int nodeCount, deleteNode, rootNode, result = 0;

    // 삭제 노드와 그 자식들을 -2로 표시
    private static void removeNode(int deleteNode) {
        for (int i = 0; i < nodeCount; i++) {
            if (graph[i] == deleteNode) {
                graph[i] = -2;
                removeNode(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        nodeCount = Integer.parseInt(br.readLine());
        graph = new int[nodeCount];
        isNotLeaf = new boolean[nodeCount];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < nodeCount; i++) {
            graph[i] = Integer.parseInt(st.nextToken());
            if (graph[i] == -1) rootNode = i; // 루트 찾기
        }

        deleteNode = Integer.parseInt(br.readLine());

        if (deleteNode == rootNode) { // 루트 삭제 시 리프 없음
            System.out.println(0);
            return;
        }

        graph[deleteNode] = -2;
        removeNode(deleteNode);

        // 부모가 된 노드 표시
        for (int i = 0; i < nodeCount; i++) {
            for (int j = 0; j < nodeCount; j++) {
                if (i == graph[j]) isNotLeaf[i] = true;
            }
        }

        // 리프 노드 세기
        for (int i = 0; i < nodeCount; i++) {
            if (!isNotLeaf[i] && graph[i] != -2) result++;
        }

        System.out.println(result);
    }
}

 

마무리하며:

대부분의 사람들은 이를 DFS를 활용해 구현한 것을 확인할 수 있었다. 하지만 입력 크기가 50으로 작기 때문에, 작성자는 굳이 재귀적 탐색을 사용하지 않고도 순차적으로 삭제 노드를 처리하고 남은 노드를 검사하는 방식으로 충분히 효율적으로 리프 노드 개수를 계산할 수 있다고 판단했다.

 

이렇게 하면 코드도 직관적이고, 루트가 0이 아니거나 한 노드에 여러 자식이 있는 경우에도 안정적으로 작동할 것이다.

 

감사합니다.