[백준/BOJ] 1068번 트리 (Java/자바) - dfs

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

1068번: 트리

 

풀이

트리 구조를 입력 받기 위해 ArrayList<>의 배열을 사용하였다.

		tree = new ArrayList[N];

처음부터 입력을 다 받아 놓고,

노드들의 부모 정보를 저장 받을 때,

애초에 삭제할 노드와 삭제할 노드의 자식 노드의 정보를 저장하지 않았음.

		for(int i=0; i<N; i++) {
			int parent = Integer.parseInt(st.nextToken());
			if(parent==-1) root = i;
			else if(i==target || parent==target) continue; // 건너뛰기
			else {
				tree[parent].add(i);
			}
		}

 

그리고 root노드부터 차례로 확인하면서

노드의 ArrayList가 비어있으면 그 노드가 리프 노드

	public static void dfs(int root) {
		if(tree[root].size()==0) {
			count++;
			return;
		}
		
		for(int i : tree[root]) {
			dfs(i);
		}
	}

(예외)

root노드와 삭제할 노드가 같다면, 마지막에 남는 리프노드는 없다.

		if(root==target) count = 0;

---

전체 코드

package bdfs;

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

public class BOJ_1068_트리 {
	static int N, target, root, count;
	static ArrayList<Integer>[] tree;
	static boolean[] visit;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		tree = new ArrayList[N];
		visit = new boolean[N];
		for(int i=0; i<N; i++) {
			tree[i] = new ArrayList<>();
		}
		target = Integer.parseInt(br.readLine());
		for(int i=0; i<N; i++) {
			int parent = Integer.parseInt(st.nextToken());
			if(parent==-1) root = i;
			else if(i==target || parent==target) continue; // 건너뛰기
			else {
				tree[parent].add(i);
			}
		}
		
		dfs(root);
		if(root==target) count = 0;
		System.out.println(count);
		
	}
	
	public static void dfs(int root) {
		if(tree[root].size()==0) {
			count++;
			return;
		}
		
		for(int i : tree[root]) {
			dfs(i);
		}
	}
}