[백준-자바] 1068번 트리 / 2022.10.18

 

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

1068번: 트리

 

 

 

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static ArrayList<Integer> list[];
    static boolean visited[];
    static int root, delete; // 루트 노드, 삭제할 노드
    static int leaf; // 리프 노드 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine()); // 노드 개수
        list = new ArrayList[N]; // 노드 관계
        visited = new boolean[N]; // 노드에 방문했는지 체크

        for (int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
        }
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) { 
            int M = Integer.parseInt(st.nextToken());
            if(M==-1){ // 입력값이 -1 이라면 루트노드 번호
                root = i;
            } else { // 부모와 자식 관계 표현
                list[M].add(i);
            }
        }

        delete = Integer.parseInt(br.readLine()); // 삭제할 노드 입력

        if(delete==root){ // 삭제할 노드가 루트 노드라면
            System.out.println(0); // 리프노드는 0개이다
        } else {
           bfs();
           System.out.println(leaf); // 리프노드 개수 출력
        }
    }
    static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(root); // 루트 노드부터 탐색 시작
        visited[root] = true; 
        while(!q.isEmpty()){
            int parent = q.poll();
            int childNum = 0;
            for(int child : list[parent]){ // 나에게 딸린 자식노드가 있다면?
                if(!visited[child] && child!=delete){ // 방문하지 않았어야하고 삭제할 노드가 아니여야함
                    visited[child] = true;
                    childNum++; // 자식노드가 있으면 리프노드가 아님
                    q.offer(child); // 다음에 탐색
                }
            }
            if(childNum==0) // 자식이 없으면
                leaf++; // 리프노드임
        }
    }
}