[BOJ] 1068 - 트리

문제 링크

1068-트리

문제 설명

입력

• 노드의 갯수
• 0번 노드부터 N-1 노드까지의 부모 노드
• 지울 노드의 번호

출력

• 리프 노드의 갯수

문제 풀이

deleteNode 와 countLeaf 모두 연쇄적으로 진행해야함!

deleteNode의 경우에는 삭제해야하는 노드의 parent값을 -2로 바꿔주고 삭제해줌
countLeaf의 경우에는 이미 삭제된 노드인지 아닌지 먼저 확인해준 뒤
삭제된 노드가 아니라면 방문했던 노드인지를 확인하며 연쇄적으로 진행

연쇄적 아주 중요 포인트!

import java.util.Scanner;

public class Main {

    static boolean[] visited;
    static int [] parent;
    static int n, delete, cnt;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        parent = new int[n];

        int root = 0;
        for (int i = 0; i < n; i++) {
            parent[i] = sc.nextInt();
            if(parent[i] == -1) root = i;
        }

        delete = sc.nextInt();
        deleteNode(delete);

        cnt = 0;
        visited = new boolean[n];
        countLeaf(root);

        System.out.println(cnt);


    }

    public static void deleteNode(int node) {
        parent[node] = -2;
        for (int i = 0; i < n; i++) {
            if(parent[i] == node) deleteNode(i);
        }
    }

    public static void countLeaf(int node) {
        boolean isLeaf = true;
        visited[node] = true;

        if (parent[node] != -2) {
            for (int i = 0; i < n; i++) {
                if (parent[i] == node && visited[i] == false) {
                    countLeaf(i);
                    isLeaf = false;
                }
            }
            if(isLeaf) cnt++;
        }
    }
}