068 : 리프 노드의 갯수 구하기

DFS같은 recursive에서

- plate를 바로 return하거나

- print하기 어렵다

> 그래서 plate를 waterfalling variable로 만들어 main에서 print한다

 

부모 > 자식노드로 진입하기만 한다면 leaf가 생기는 것이고,

 

특정 노드(우선은 부모 노드로 간주)에서 자식으로 진입되는 게 아무것도 없다면(여기서는 deleteTarget 포함) plate 추가

 

 

 

 

부모-자식 쌍으로 유입하되 root는 별도 관리

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

root와 deleteTarget Lock 별도 관리

 

 

 

 

 

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static ArrayList<Integer>[] TP;
    static boolean[] visited;
    static int deleteTarget;
    static int plate;

    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();

        // D2F
        TP = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            TP[i] = new ArrayList<>();
        }
        int root = 0;
        for (int i = 0 ; i < V; i++) {
            int p = sc.nextInt();
            if (p == -1) {
                root = i;
            } else {
                TP[p].add(i);
                TP[i].add(p);
            }
        }
        deleteTarget = sc.nextInt();
        visited = new boolean[V];

        // OP + OEC
        if (deleteTarget == root)  {
            System.out.println(0);
        } else {
            DFS(root);
            System.out.println(plate);
        }
    }

    static void DFS(int now) {

        visited[now] = true;

        int leaf = 0;
        for (int connected : TP[now]) {
            if (!visited[connected] && connected != deleteTarget) {
                leaf++;
                DFS(connected);
            }
        }
        if (leaf == 0)
            plate++;
    }
}