[백준] 트리 - 골드5, 트리(Tree)

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

1068번: 트리

 

상당히 헷갈리는 문제였습니다.

그래프를 만들어서 진행했습니다.

 

 

기억해야할점들입니다.

첫번째, 삭제 처리된 노드를 dfs가 들어가기 전에 먼저 처리해야합니다.

이렇게 처리해야만 dfs가 삭제된 노드를 아예 없다고 인식하여 리프노드로 인식됩니다.

 

두번째, 삭제 노드delete는 무조건 0번 노드가 아닙니다.

그러므로 루트노드의 번호 비교해야합니다.

if(delete == root.index) {
    System.out.println(answer);
    return ;
}

 

코드입니다.

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	static Node root;
	static int answer=0;
	static int delete=0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		for(int i=0;i<N;i++) {
			graph.add(new ArrayList<Node>());
		}
		
		for(int i=0;i<N;i++) {
			int parent = sc.nextInt();
			if(parent == -1) {root = new Node(i); }
			else graph.get(parent).add(new Node(i));
		}
		
		delete = sc.nextInt();
		if(delete == root.index) {
			System.out.println(answer);
			return ;
		}
		
		for(int i=0;i<graph.size();i++) {
			for(int j=0;j<graph.get(i).size();j++) {
				if(graph.get(i).get(j).index == delete) {
					graph.get(i).remove(j);
				}
			}
		}
 
		dfs(root);
		System.out.println(answer);
	}
	static void dfs(Node start) {
		if(start == null) return;
		if(graph.get(start.index).size() == 0) answer++;
 
		for(int i=0;i<graph.get(start.index).size();i++) {
			dfs(graph.get(start.index).get(i));
		}
		
	}
	
	static class Node{
		int index;
		public Node(int index) {
			this.index = index;
		}
	}
 
}