1068번) 트리 - 그래프

문제 출처 : https://www.acmicpc.net/problem/1068

import java.util.Scanner; public class Q1068 { static int[][] nodes; static Scanner sc; public static void main(String[] args) { sc = new Scanner(System.in); int number = sc.nextInt(); nodes = new int[number][2]; //0.부모노드 1.자식노드 개수 for ( int i = 0; i < number; i++ ) { nodes[i][0] = sc.nextInt(); } setNode(number); //자식노드 개수 세기 removeNode(sc.nextInt()); //노드 지우기 System.out.println(getLeafNode()); sc.close(); } static void setNode(int number) { for ( int i = 0; i < number; i++ ) { for ( int j = 0; j < number; j++ ) { if ( nodes[j][0] == i ) { nodes[i][1] += 1; } } } } static void removeNode(int startNode) { if ( nodes[startNode][0] != -1 ) { //현재노드가 루트 노드가 아니면 nodes[nodes[startNode][0]][1]--; //부모 노드에서 자식 개수 하나 제거 } nodes[startNode][0] = -2; //부모 노드를 -2로 바꿈으로 노트 제거 if ( nodes[startNode][1] != 0 ) { //자식노드가 있으면 for ( int i = 0; i < nodes.length; i++ ) { //자식노드를 찾아서 제거 if ( nodes[i][0] == startNode ) { removeNode(i); } } } } static int getLeafNode() { int leafNode = 0; for ( int i = 0; i < nodes.length; i++ ) { if ( nodes[i][0] != -2 && nodes[i][1] == 0 ) { //지운 노드(부모가 -2)가 아니면서 leaf 노드일 경우 leafNode++; } } return leafNode; } }