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

🔗 1068번 : 트리
● Java 풀이
● 시간 제한 2초
● 메모리 제한 128 MB

문제

 

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.

 

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

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

 

풀이

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

public class Main {
    private static int N, delete, LEAF_NODE;
    private static List<Integer>[] nodeList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());  // 노드 개수
        int root = 0;  // 루트 노드를 담을 변수
        nodeList = new ArrayList[N];  // 자식 List를 담을 List 배열

        StringTokenizer st = new StringTokenizer(br.readLine());  // 노드 받기
        int parent;  // 해당 노드의 부모 값 담을 임의의 변수 선언
        for (int i = 0; i < N; i++) {
            parent = Integer.parseInt(st.nextToken());  // i 노드가 가리키는 부모 노드
            if (parent < 0) {  // -1일 경우
                root = i;  // 루트 노드 초기화
                continue;
            }

            if (nodeList[parent] == null) nodeList[parent] = new ArrayList<>();
            nodeList[parent].add(i);  // 부모 노드에 자식 노드 담기
        }
        delete = Integer.parseInt(br.readLine());  // 삭제할 노드 변수 초기화
        if (delete == root) {  // 루트 노드가 삭제 되었을 경우
            System.out.println(0);  // 노드의 개수 0
            return;
        }

        dfs(root);  // DFS로 리프노드 탐색
        System.out.println(LEAF_NODE);
    }

    private static void dfs(int node) {
        // 원래 리프노드였거나, 자식 노드 하나가 삭제되어 리프노드가 되었을 때
        if (nodeList[node] == null || (nodeList[node].size() == 1 && nodeList[node].get(0) == delete)) {
            //System.out.println(node + "번 노드는 리프노드.");
            LEAF_NODE++;  // 리프노드 개수 추가
            return;  // 탐색 끝내기
        }

        for (int child : nodeList[node]) {  // 자식 노드 탐색
            if (child == delete) continue;  // 삭제된 노드일 경우 탐색 X
            dfs(child);  // 자식 노드의 자식 탐색 재귀 호출
        }
    }
}

 

풀었다고 말하기도 민망한 너무 쉬웠던 문제...

최근 골드 3 문제를 풀어버릇 해서 그런지, 테스트케이스가 많아서 그런지, 아니면 등급 설정이 잘못 되어있는 건지.

그냥 기본 DFS + 삭제 노드 조건 체크만 해주면 성공하는 문제였다.

 

자존심이 상하는 건, 백준 문제 밑 알고리즘 분류를 무심코 봐버렸다는 거다.

그래서 풀이가 막히지 않고 술술 나올 수 있었다.

코딩 테스트를 풀 때도 문제 이해 자체에서 좀 막히는 것 같은데, 문제를 보고 무슨 알고리즘으로 풀어야하는지에 대해 빠른 습득을 학습해야겠다.