백준 1068 트리 Java [DFS]

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

1068번: 트리

 

예제에 없는 조건만 찾으면 빨리 해결할 수 있다

먼저 루트가 0번 인덱스가 고정이 아니다

어떤 노드의 자식 노드가 제거됐을 때 남은 자식 노드가 없으면 리프 노드가 된다

 

입력값을 이용하여 먼저 root를 찾아주고 인덱스별 자식 노드를 children에 담아주었다

이 때 삭제될 노드는 자식 노드로 넣어주지 않았다

 

3번 예제가 루트 노드와 삭제 노드가 같은 경우인데

이런 경우에는 큐에 값을 넣지 않아 dfs가 바로 끝나게 만든다

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] nodes = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int del = Integer.parseInt(br.readLine());
        int root = 0, result = 0;
        Queue<Integer> queue = new LinkedList<>();
        ArrayList<Integer>[] children = new ArrayList[N];
        for (int n = 0; n < N; n++) children[n] = new ArrayList<>();
        for (int n = 0; n < N; n++) {
            if (nodes[n] == -1) root = n;
            else if (n != del) children[nodes[n]].add(n);
        }
        if (del != root) queue.add(root);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (children[node].size() == 0) result++;
            else {
                for (int child : children[node]) {
                    queue.add(child);
                }
            }
        }
        System.out.println(result);
    }
}