[백준] 트리/자바

문제         

레벨: G5
알고리즘: DFS
풀이시간: 2시간
힌트 참조 유무: 유 

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

1 번째 시도   

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


public class Main {

    static ArrayList<Node> list = new ArrayList<>();

    static boolean[] visited;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        int N = Integer.parseInt(br.readLine());
        visited = new boolean[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int i = 0;
        while (st.hasMoreTokens()) {
            int data = Integer.parseInt(st.nextToken());
            if (data != -1) {
                if (i % 2 == 0) {
                    list.get(data).addRight(i);
                } else {
                    list.get(data).addLeft(i);
                }
            }
            list.add(new Node(i));
            i++;
        }
        Node removeNode = list.get(Integer.parseInt(br.readLine()));

        dfsA(removeNode);
        dfsB(list.get(0));

        System.out.println(answer);
    }

    public static void dfsA(Node node) {
        visited[node.data] = true;


        if (node.left != null && node.left > 0 && node.left < list.size())
            dfsA(list.get(node.left));
        if (node.right != null && node.right > 0 && node.right < list.size())
            dfsA(list.get(node.right));
    }

    public static void dfsB(Node node) {
        if (node == null) return; // Added null check for safety.

        if(node.left == null && node.right == null) {
            answer++;
        }

        if (node.left != null && node.left < list.size() && !visited[node.left]) {
            dfsB(list.get(node.left));
        }
        if (node.right != null && node.right < list.size() && !visited[node.right]) {
            dfsB(list.get(node.right));
        }
    }


    public static class Node {
        Integer data;
        Integer left;
        Integer right;

        public Node(int data) {
            this.data = data;
        }

        public void addLeft(int left) {
            this.left = left;
        }

        public void addRight(int right) {
            this.right = right;
        }

        public boolean existLeft() {
            return this.left != null ? true : false;
        }

        public boolean existRight() {
            return this.right != null ? true : false;
        }
    }
}

예제 3번 테스트

예제 4번 테스트

혼자 테스트해 본 것은 통과했지만 
제출해보니 IndexOutOfBounds가 났다

오류가 발생하는 곳

핵심 문제는 노드가 추가되었는지 확인하기 전에 list.get(data)가 유효하다는 가정이다. 입력 순서나 논리가 약간 변경(자식 노드가 부모 노드보다 먼저 입력될 때)되면아직 초기화되지 않은 인덱스(list 앞에 list.get(data))에 액세스하려고 시도하게 된다. .add(new Node(data))), IndexOutOfBoundsException으로 이어진다.

 

2차시도     

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

public class Main {

    static int N, root, ans;
    static int[] parent;
    static boolean[] isVisited;

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

        N = Integer.parseInt(br.readLine());
        parent = new int[N];
        
        stringTokenizer = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N ;i++){
            int x = Integer.parseInt(stringTokenizer.nextToken());
            parent[i] = x;
            if(x == -1) root = i;
        }

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

        removeNode(remove);

        ans = 0;
        isVisited = new boolean[N];
        countLeaf(root);
        
        System.out.println(ans);
    }

    private static void countLeaf(int idx) {
        boolean isLeaf = true;
        isVisited[idx] = true;
        if(parent[idx] != -2){
            for(int i = 0 ; i < N ; i++){
                if(parent[i] == idx && !isVisited[i]){
                    countLeaf(i);
                    isLeaf = false;
                }
            }
            if(isLeaf)
                ans++;
        }

    }

    private static void removeNode(int idx) {
        parent[idx] = -2;

        for(int i = 0 ; i < N ; i++){
            if(parent[i] == idx)
                removeNode(i);
        }
    }
}

배운점