[BOJ_1068] 트리

설명

---

이전에 같은 문제를 풀었던 이력이 있어서 풀었는데 거의 이전과 동일한 풀이법이 나와서 조금 놀랐다. 트리 형태를 갖추고 해당 노드를 제외하고 리프노드의 갯수를 찾기 위한 로직인데 root가 지워지면 리프노드의 갯수를 셀 수 있는 트리의 형태가 되지 않고 이를 제외한 나머지 경우에서는 깊이 우선 탐색 법으로 탐색을 하면서 찾아서 리프 노드의 갯수를 세는 형식으로 풀었다.

 

코드

---

package tree;

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

public class BOJ_1068 {
    static boolean visited[];
    static int root;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());

        List<Integer>[] nodeList = new ArrayList[N];

        tk = new StringTokenizer(in.readLine()," ");

        for (int i = 0; i < N; i++){
            nodeList[i] = new ArrayList<>();
        }
        visited = new boolean[N];
        root = -1;

        for (int i = 0; i < N; i++){
            int parents = Integer.parseInt(tk.nextToken());
            if (parents == -1){
                root = i;
            }else {
                nodeList[parents].add(i);
            }
        }

        tk = new StringTokenizer(in.readLine()," ");
        int where = Integer.parseInt(tk.nextToken());
        if(where == root){
            System.out.println(0);
        }else {
            visited[where] = true;
            System.out.println(dfs(root, nodeList));
        }
    }

    private static int dfs(int where, List<Integer>[] nodeList) {
        int cnt = 0;
        visited[where] = true;
        for (int i : nodeList[where]){
            if(!visited[i]) {
                visited[i] = true;
                cnt += dfs(i, nodeList);
            }
        }
        if(cnt != 0){
            return cnt;
        }else {
            return 1;
        }
    }
}

1068번: 트리