[백준 1068번] 트리 - JAVA

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

1068번: 트리

풀이

사용한 알고리즘 : DFS

 

풀이전략

1. 이중 ArrayList를 사용하여 각 노드가 가지고 있는 자식 노드의 번호를 저장한다.

2. 각 노드들의 부모 노드 번호를 저장하는 배열을 만든다.

3. 제거한 노드의 부모노드에 대응되는 ArrayList에서 제거한 노드의 번호를 삭제한다.

4. DFS를 통해 트리를 탐색하고, 방문한 노드 중 자식 노드가 없는 경우 count를 1씩 더한다.

 

제출코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean visited[];
    static int count=0;
    static int removeNode;
    static int root=0;
    static int parent[];

    static void dfs(int x){
        visited[x]=true;

        if(graph.get(x).size()==0) count++;
        for(Integer a : graph.get(x)){
            if(visited[a]==false){
                dfs(a);
            }
        }
    }
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N=Integer.parseInt(br.readLine());
        for(int i=0;i<N;++i){
            graph.add(new ArrayList<>());
        }
        visited = new boolean[N];
        parent = new int[N];
        for(int i=0;i<N;++i){
            parent[i]=i;
        }
        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;++i){
            int temp = Integer.parseInt(st.nextToken());
            parent[i]=temp;
            if(temp==-1) root=i;
            else graph.get(temp).add(i);
        }

        removeNode = Integer.parseInt(br.readLine());
        if(removeNode!=root){
            graph.get(parent[removeNode]).remove(Integer.valueOf(removeNode));
            dfs(root);
        }

        System.out.println(count);
    }
}