boj 1068 트리

www.acmicpc.net/problem/1068

1068번: 트리

각 노드의 부모노드가 입력으로 주어집니다. (루트노드인 경우에는 -1이 주어집니다.)

그리고 삭제할 노드가 주어집니다.

노드를 삭제하면 해당 노드의 자식노드들까지 모두 삭제됩니다.

노드를 삭제한 후의 리프노드 갯수를 구하는 문제입니다.

 

입력이 들어오면 ArrayList로 그래프를 만들어줍니다.

그리고 입력으로 -1이 주어지면 루트노드이므로 저장해둡니다.

 

이제 root를 시작으로 dfs를 돌려줍니다.

만약 v가 삭제할 노드면 바로 리턴시켜주고,

v의 자식이 없으면 (list[v].size() == 0) 리프노드입니다. => ans++

v의 자식이 1개이고 그게 삭제할 노드면 v는 리프노드가 됩니다. => ans++

위의 예외처리만 해주고 dfs를 돌립니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer> list[];
    static int N, deleteNode, root, ans;
 
    static void dfs(int v) {
        if (v == deleteNode)
            return;
 
        if (list[v].size() == 0) {
            ans++;
            return;
        }
 
        for (int i = 0; i < list[v].size(); i++) {
            int next = list[v].get(i);
            
            if(list[v].size()==1 && next == deleteNode) {
                ans++;
                return;
            }
            
            dfs(next);
        }
    }
 
    static void input() throws Exception {
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList[N];
        for (int i = 0; i < N; i++)
            list[i] = new ArrayList<>();
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(st.nextToken());
            if (x != -1)
                list[x].add(i);
            else
                root = i;
        }
 
        st = new StringTokenizer(br.readLine());
        deleteNode = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(root);
        System.out.println(ans);
    }
}