[백준]1068: 트리 - JAVA

[백준]1068: 트리

www.acmicpc.net/problem/1068

1068번: 트리

풀이

부모 인덱스를 입력받고, 노드를 삭제한 후 리프 노드를 count하는 문제로 깊이 우선 탐색 방법을 적용하여 문제를 풀었다. (약간 변형된 DFS문제라고 생각한다.) 

 

노드를 삭제할 때에는 재귀 함수를 활용하여 현재 노드의 부모 인덱스가 삭제된 노드라면 연쇄적으로 삭제가 일어나도록 구현해 주었다.

 

리프노드를 카운트 할 때에는 깊이 우선 탐색을 활용하여 현재 노드를 부모로 가지는 노드가 하나라도 존재한다면 자식 노드를 연쇄적으로 탐색하도록 하였다. 재귀 함수 속에서 자식 노드가 하나라도 존재하는지를 기록해 주기 위해 boolean 타입의 변수를 하나 생성해 주었다. 자식 노드가 없다면 리프노드의 카운트를 증가시켰다.

 

재미있는 문제였다!

 

코드

import java.util.*;
 
public class Main {
 
    static int n, delete;
    static int[] parent;
    static int count;
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        parent = new int[n];
        int root = 0;
        for(int i = 0; i < n; i++) {
            parent[i] = scan.nextInt();        
            if(parent[i] == -1) root = i;
        }
        delete = scan.nextInt();
        
        deleteNode(delete);
            
        count = 0;
        visited = new boolean[n];
        countLeaf(root);
            
        System.out.println(count);
    }
    
    public static void deleteNode(int d) {
        parent[d] = -2; //삭제된 노드 -2로 표시
        for(int i = 0; i < n; i++) {
            if(parent[i] == d) {
                deleteNode(i);
            }
        }
    }
    
    public static void countLeaf(int s) {
        boolean isLeaf = true;
        visited[s] = true;
        if(parent[s] != -2) {
            for(int i = 0; i < n; i++) {
                if(parent[i] == s && visited[i] == false) {
                    countLeaf(i);
                    isLeaf = false;
                }
            }
            if(isLeaf) count++;
        }
    }
}