[자바] 백준 1068번: 트리

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

1068번: 트리

 

---

트리에서 삭제할 노드를 입력받고

삭제할 노드와 그 하위 노드들의 parent[]값을 -2로 바꾸었다.

 

이후, 리프노드의 수를 출력한다.

 

리프노드는 재귀함수로 작성했는데,

자식이 없는경우 => 자신이 리프노드이므로 1 리턴

자식이 있는경우 => 자식노드들의 리프노드의 합 리턴

한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1068 {

	static int n;
	static int[] parent;
	static int[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		parent=new int[n];
		visited=new int[n];
		
		int root=0;
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			parent[i]=Integer.parseInt(st.nextToken());
			if(parent[i]==-1)
				root=i;
		}
		
		int delete = Integer.parseInt(br.readLine());
		parent[delete]=-2;
		for(int i=0;i<n;i++) {
			int now=i;
			while(parent[now]!=-1) {
				if(parent[now]==-2) {
					parent[now]=-2;
					break;
				}
				now=parent[now];
			}
		}
		
		System.out.println(count_leaf(root));
		
		
	}
	static int count_leaf(int root) {
		boolean isLeaf=true;
		visited[root]=1;
		int count=0;
		if(parent[root]==-2)
			return 0;
		for(int i=0;i<parent.length;i++) {
			if(parent[i]==root && visited[i]==0) {
				//나를 부모로 하는 노드가 있음
				isLeaf=false;
				count+=count_leaf(i);
			}
		}
		
		if(isLeaf==true)
			return 1;
		else
			return count;
		
		
	}

}