[JAVA] 백준 1068 트리_트리

 

문제 : 

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

 

접근 : 

 

  - 입력 받은 수를 배열에 넣는다.

 

  - 지워야할 수를 저장한 후, 입력 받은 배열로 그래프를 만든다.

 

 - 만약 배열의 인덱스나 배열의 값이 지워야할 수 이라면 그래프로 만들지 않고 다음 수로 넘어간다.

 

 - root 와 지워야할 수가 같다면 0을 출력, 다르면 root 부터 리프노드의 수를 DFS 로 계산한다.

 

 - 탐색이 끝나면 리프노드 수를 출력한다.

 

 

코드 구현 : 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    private static Map<Integer, List<Integer>> child;

    static int dfs(int now){
        int res = 0;
        if(child.get(now) == null) return 1;

        for(int n : child.get(now)) res += dfs(n);

        return res;
    }

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

        int n = Integer.parseInt(br.readLine());
        String[] inputs = br.readLine().split(" ");
        child = new HashMap<>();
        int root = 0;
        int[] nums = new int[n];
        for(int i = 0 ; i < n ; i++) nums[i] = Integer.parseInt(inputs[i]);
        int removed = Integer.parseInt(br.readLine());

        for(int i = 0 ; i < n ; i++){

            if(nums[i] == -1){
                root = i;
                continue;
            }

            if(nums[i] == removed || i == removed) continue;

            if(child.containsKey(nums[i])){
                child.get(nums[i]).add(i);
            }else{
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                child.put(nums[i], temp);
            }
        }

        System.out.println( root == removed ? 0 :dfs(root));
        br.close();
    }
}