백준 1056 트리

백준 1068 - 트리
엄청나게 삽질하며 푼 문제이다.
물론 내 잘못이긴 했지만, 문제가 너무 명확하지 않은 탓에 반례를 생각하기 어려웠다.

DFS로 루트부터 탐색하고, 자식 노드가 없을 경우 리프 노드로 취급하는 식으로 풀었다.

import java.io.*;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N, leaves, delete, root;
    static int[][] graph;
    static boolean[] isVisited;

    static void dfs(int v) {
        if(v == delete) {
            return; // root 노드가 delete된 노드일 경우, 아무것도 하지말고 리턴해서 0을 출력하게 한다.
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(v);
        isVisited[v] = true;
        int child = 0;
        while(!stack.isEmpty()) {
            for(int i = 0; i < N; i++) {
            	//v->i 로 갈 수 있고, i 에 방문하지 않았으며, i 가 delete된 노드가 아닐 경우에 스택에 추가하고 dfs(i)를 돌린다
                if(graph[v][i] == 1 && !isVisited[i] && i != delete) {
                    child++;
                    System.out.printf("%d -> %d\n", v, i);
                    stack.push(i);
                    dfs(i);
                }
            }
            stack.pop();
        }
        System.out.printf("v = %d child = %d\n",v , child);
        if(child == 0) {
            leaves++; // 위의 과정에서 child가 추가 되지 않았다면 리프노드의 개수를 추가해준다.
        }
    }

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        isVisited = new boolean[N];
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        leaves = 0;
        root = 0;
        delete = -1;
        graph = new int[N][N];
        for(int i = 0 ; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if(parent == -1) {
                root = i;
                continue;
            }
            graph[parent][i] = 1;
            graph[i][parent] = 1;
        }
        delete = Integer.parseInt(bufferedReader.readLine());
        dfs(root);
        System.out.println(leaves);
        bufferedReader.close();
    }
}

내가 했던 실수는,

if(parent == -1) {
    root = i;
    parent = 0;
}

로 했던 것이다. 만약 루트 노드가 0번이 아닌 경우, 루트 노드인 i번과 0번이 이어지기 때문에 문제가 발생했다. 저쪽은 맨처음 코드 짤때 잘못 짰던 건데, 이거 때문에 몇시간을 썼는지,...