[백준] 1068번 : 트리 Gold5(골드5) - JAVA[자바]

[Gold V] 트리 - 1068

문제 링크

성능 요약

메모리: 11564 KB, 시간: 76 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

제출 일자

2024년 1월 16일 00:09:22

문제 설명

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

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

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

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

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

입력

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

출력

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

 

접근 방법

1. 언제 루트 노드가 들어올지 모른다. 그러므로 배열에 먼저 전부 받아주면서 루트 노드를 기억해준다.

2. 만약 삭제되는 노드가 루트 노드라면 답은 0이다.

3. DFS를 통해서 삭제되는 노드의 값을 -1로 바꿔준 뒤 삭제되는 노드를 부모 노드로 하는 노드가 있다면 재귀 호출을 통해 전부 -1로 지워준다.

4. 연결이 끊기지 않는 노드에 한해서 자신을 부모노드로 사용하고 있는 노드가 있는지 확인해주고 없다면 리프노드 카운트를 더해준다.

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

public class Main {
    static int[] nodes;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 노드들을 입력 받는 배열
        nodes = new int[n];
        // 루트 노드를 저장하기 위한 변수
        int rootIdx = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            // 값을 입력 받으면서 루트 노드를 찾음
            nodes[i] = Integer.parseInt(st.nextToken());
            if(nodes[i] == -1) rootIdx = i;
        }

        int deleteIdx = Integer.parseInt(br.readLine());
        // 만약 루트 노드를 지운다면 정답은 0
        if(rootIdx == deleteIdx){
            System.out.println(0);
        }else{
            // 루트 노드가 아니라면 지워준다.
            deleteNode(deleteIdx);
            // deleateNode를 제거한 뒤 리프 노드를 세준다.
            System.out.println(countLeafNode());
        }
    }

    // 리프 노드의 개수를 세어주는 메서드
    private static int countLeafNode() {
        int count = 0;
        // 전체를 보면서 값이 -1인 노드(delete메서드를 통해서 지워진 노드)를 제외하고 리프 노드가 있는지 확인한다.
        for (int i = 0; i < nodes.length; i++) {
            // 연결이 끊겨있다면 넘어간다.
            if(nodes[i] == -2) continue;

            boolean leaf = true;
            // 전체 노드를 확인하면서 현재 노드를 부모로 하는게 있는지 확인한다.
            for (int j = 0; j < nodes.length; j++) {
                if(nodes[j] == i) {
                    leaf = false;
                    break;
                }
            }
            // 없다면 count 증가
            if(leaf) count++;
        }
        return count;
    }

    // deleteIdx를 지워준 뒤 현재 노드를 부모노드로하는 노드가 있다면 지워준다.
    private static void deleteNode(int deleteIdx) {
        // 삭제해야 할 값은 -2를 넣어줌(-1은 루트 노드가 사용함)
        nodes[deleteIdx] = -2;

        // 현재 deleteIdx를 부모노드로 하는 노드 또한 전부 지워주어야한다.
        for (int i = 0; i < nodes.length; i++) {
            if(nodes[i] == deleteIdx){
                deleteNode(i);
            }
        }
    }
}