[백준 Gold 5] 1068 트리 - Java

문제링크 : https://www.acmicpc.net/problem/1068

1068번: 트리

 

접근 과정 : 

• 트리에 속한 노드 중 하나를 삭제했을 때, 남아있는 리프노드의 갯수를 구하는 문제이다.
• 노드를 삭제하면 그 노드의 자식 노드들도 같이 삭제된다.
• 우선 자식노드를 저장하는 List<List<Integer>> 를 생성했다.
• 그리고 삭제할 노드부터 그 이하 자식노드를 모두 boolen[] removed에 체크했다.
• 이제 0번 노드부터 N-1번 노드까지 순회하면서, 현재 리프노드인 것만 계산했다.

소스 코드 및 결과 :

package BOJ;

/* 
    트리
*/

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

public class BOJ1068 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        children = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            children.add(new ArrayList<>());
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if (parent != -1) {
                children.get(parent).add(i);
            }
        }

        removed = new boolean[N];

        int x = Integer.parseInt(br.readLine());

        removeNode(x);

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (removed[i]) {
                continue;
            }

            if (children.get(i).isEmpty()||(children.get(i).size() == 1 && removed[children.get(i).get(0)])) {
                count++;
            }

        }

        System.out.println(count);

    }

    static List<List<Integer>> children;
    static boolean[] removed;

    static void removeNode(int x) {

        removed[x] = true;

        for (int child : children.get(x)) {
            removeNode(child);
        }
    }
}

 

P.S 

어떤 노드를 기준으로 해당 노드의 부모와 자식을 모두 저장할 수 있는 자료구조를 사용한다면 더 좋지 않을까??