[BOJ1068] 트리

트리의 기본 개념을 묻는 문제였다.

 

처음에 주어지는 트리가 이진트리인 줄 알고 배열로 자료구조를 구성하려고 했다가 이진트리가 아닌 걸 깨닫고 Node 클래스를 만들어 childs라는 Integer 배열로 부모 자식 관계를 나타내 주었다.

첫 시도(실패)

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

public class Main {
	
	static int N, removeNode, root, answer;
	static Node[] tree; 
	
	static class Node{
		int num;
		boolean isActive;
		ArrayList<Integer> childs = new ArrayList<>(); 
		
		public Node(int num) {
			this.num = num; 
			this.isActive = true; 
		}
	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		
		N = Integer.parseInt(br.readLine()); 
		
		tree = new Node[N]; 

		// 트리 초기화
		for(int i=0; i<N; i++) {
			tree[i] = new Node(i); 
		}
		
		st = new StringTokenizer(br.readLine()); 
		
		
		for(int i=0; i<N; i++) {
			int parent = Integer.parseInt(st.nextToken());
			
			if(parent == -1) {
				root = i;
				continue; 
			}
			
			tree[parent].childs.add(i); 
			
		}
		removeNode = Integer.parseInt(br.readLine());
		tree[removeNode].isActive = false;
		
		dfs(root); 
		
		System.out.println(answer);
		
		 
	}
	
	static void dfs(int idx) {
		Node curNode = tree[idx];
		if(!curNode.isActive) return; 
		
		if(curNode.childs.isEmpty()) {
			answer++; 
			return;
		}
		
		for(int next : curNode.childs) {
			dfs(next);
		}
	}

}

 

🔥 반례와 틀린 이유

2
-1 0
1

AC : 1
WA : 0

 

나는 리프노드를 체크하는 조건을 childs 배열의 사이즈만 가지고 판단하였다. 하지만 자식노드를 하나 가지고 있지만 그 노드가 삭제된 노드라면 해당 노드도 리프노드라고 판단할 수 있을 것이다. 따라서 boolean 값을 추가해 해당 경우를 판별하는 로직을 추가하였다.

 

두 번째 시도(성공)

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

public class Main {
	
	static int N, removeNode, root, answer;
	static Node[] tree; 
	
	static class Node{
		int num;
		boolean isActive;
		ArrayList<Integer> childs = new ArrayList<>(); 
		
		public Node(int num) {
			this.num = num; 
			this.isActive = true; 
		}
	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		
		N = Integer.parseInt(br.readLine()); 
		
		tree = new Node[N]; 

		// 트리 초기화
		for(int i=0; i<N; i++) {
			tree[i] = new Node(i); 
		}
		
		st = new StringTokenizer(br.readLine()); 
		
		
		for(int i=0; i<N; i++) {
			int parent = Integer.parseInt(st.nextToken());
			
			if(parent == -1) {
				root = i;
				continue; 
			}
			
			tree[parent].childs.add(i); 
			
		}
		removeNode = Integer.parseInt(br.readLine());
		tree[removeNode].isActive = false;
		
		dfs(root); 
		
		System.out.println(answer);
		
		 
	}
	
	static void dfs(int idx) {
		Node curNode = tree[idx];
		if(!curNode.isActive) return; 
//		System.out.println(curNode.num);
		
		if(curNode.childs.isEmpty()) {
			answer++; 
			return;
		}
		
		boolean flag = true; 
		
		for(int next : curNode.childs) {
			// 활성화 되어있지 않다면
			if(!tree[next].isActive) continue;
			flag = false; 
			dfs(next);
		}
		
		if(flag) answer++; 
	}

}

 

조금 지저분하긴 한데 flag boolean 변수를 두어 자식이 있더라도 다음 자식으로 순회하지 않는다면 answer를 추가하도록 로직을 추가하였다. 이런 방법도 있을 것이도 다른 방법으로는 지우는 자식의 부모노드의 childs 리스트에 접근해 해당 자식노드를 삭제하는 방법도 유효할 거 같다.