[BOJ 1068] 트리 (Java, DFS)

 

---

문제 링크 

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

1068번: 트리

---

문제 풀이

- 인접 리스트로 트리 정의

- 제거할 노드(REMOVE_NODE)를 인접 리스트 순회하면서 제거

- LEAF 노드 배열 값을 갱신하며 DFS 탐색

- 최종적으로 ROOT 노드의 있는 값을 출력하면 됨

- 시간 복잡도 : O(N) , (N <= 50)

---

제출 코드

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

public class Main {

    static int N, REMOVE_NODE, ROOT;

    static List<Integer>[] adj;

    static int[] LEAF;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        LEAF = new int[N];

        adj = new ArrayList[N];
        for(int i = 0; i < N; i++) adj[i] = new ArrayList<>();

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

            adj[parent].add(i);
        }

        REMOVE_NODE = Integer.parseInt(br.readLine());
    }

    static void dfs(int node) {
        if(adj[node].isEmpty()) {
            LEAF[node] = 1;
            return;
        }

        for(int child : adj[node]) {
            dfs(child);
            LEAF[node] += LEAF[child];
        }
    }

    static void pro() {
        for(int i = 0; i < N; i++) {
            if(adj[i].contains(REMOVE_NODE)) {
                adj[i].remove(adj[i].indexOf(REMOVE_NODE));
            }
        }

        if(ROOT != REMOVE_NODE) dfs(ROOT);

        System.out.println(LEAF[ROOT]);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}