백준 1068 (트리) - java

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

1068번: 트리

입력 중 -1 인 경우 : 해당 index 번째 노드가 root 노드

마지막에 입력되는 노드 : target

 

과정

1. target 노드부터 아래로 탐색하면서 방문 처리를 한다.
2. root 노드부터 탐색하면서 방문처리 되지 않은 리프 노드의 개수를 구한다.

코드

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

public class Main {

    static int n = 0;
    static int target = 0;
    static int[] p;

    static boolean[] visit;

    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        p = new int[n+1];
        visit = new boolean[n+1];

        ArrayList<Integer>[] tree = new ArrayList[n+1];
        for(int i=0;i<n;i++)
        {
            tree[i] = new ArrayList<>();
        }

        int root = 0;
        for(int i=0;i<n;i++)
        {
            p[i] = Integer.parseInt(st.nextToken());

            if(p[i] == -1) {
                root = i;
                continue;
            }

            tree[p[i]].add(i);
        }
        st = new StringTokenizer(br.readLine(), " ");
        target = Integer.parseInt(st.nextToken());

        visit[target] = true;
        Fs(target , tree); // 방문 처리
        Ss(root,tree); // 루트부터 검사

        System.out.println(result);

        br.close();
    }

    static void Fs(int cur,ArrayList<Integer>[] tree)
    {
        for(int next : tree[cur])
        {
            if(!visit[next])
            {
                visit[next] = true; // 방문 처리
                Fs(next,tree); // 자식 노드 탐색
            }
        }
    }

    static void Ss(int cur,ArrayList<Integer>[] tree)
    {
        if(visit[cur]) // 이미 방문했던 노드라면 종료
            return;

        if(tree[cur].size() == 0) 
        {
            result = result + 1; // 리프 노드
            return;
        }

        int count = 0;
        for(int next : tree[cur])
        {
            if(visit[next]) {
                count = count + 1;
                continue;
            }

            Ss(next,tree);
        }

        if(count == tree[cur].size())
        {
            result = result + 1; // 자식이 있지만 모두 방문처리되었다면 -> 리프 노드
        }
    }
    
}