백준 1068 자바

<문제>

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

1068번: 트리

 

<풀이>

parent라는 리스트에 입력한 값을 넣는다. 이후 노드를 삭제하는 함수를 만든다. 이때 재귀함수를 이용해서 해당 부모를 가진 노드를 삭제한다. 삭제할 때는 값을 -2로 바꿔준다. 또한 방문했던 값들은 visited 배열을 true로 바꿔준다.

삭제 이후에 리프노드 개수를 파악하는 함수를 만든다. visited가 true인것은 확인하지 않고 리프노드를 체크하는 함수를 호출한다.

리프노드를 체크하는 함수에서 체크하는 노드는 visited를 true로 바꿔주고, 노드의 부모가 있는지 확인한다.

 

<코드>

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

public class Main {

    public static int n,remove;
    public static int[] parent;
    public static boolean[] visited;

    public static void main(String[] args)throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       n = Integer.parseInt(br.readLine());
       parent = new int[n];
       visited = new boolean[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for(int i = 0; i < n; i++) {
           parent[i] = Integer.parseInt(st.nextToken());
       }
       remove = Integer.parseInt(br.readLine());
       removeNode(remove);
        System.out.println(cntLeafNode());

    }

    public static void removeNode(int r) {
        visited[r] = true;
        parent[r] = -2;

        for(int i = 0; i < n; i++) {
            if(parent[i] == r) removeNode(i);
        }
    }

    public static int cntLeafNode() {
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(visited[i]) continue;
            if(ifLeafNode(i)) cnt++;
        }
        return cnt;
    }

    public static boolean ifLeafNode(int index) {
        visited[index] = true;
        boolean result = true;
        for(int i = 0; i < n; i++) {
            if(parent[i] == index) {
                result = false;
                break;
            }
        }
        return result;
    }

}