백준 1068번: 트리 [JAVA]

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

1068번: 트리

• 풀이 1 - 배열 사용

루트 노드부터 시작하여 자식을 탐색하는 재귀 함수를 작성한다. 자식이 없을 경우, 리프 노드의 개수를 늘리고 재귀를 종료한다.

지울 노드의 자식들은 같이 사라지므로 지울 노드의 방문 여부를 true로 바꿔놓으면 그 아래 자식들은 탐색하지 않을 수 있다.

주어진 입력이 자식이 아닌 부모 노드의 인덱스를 알려주기 때문에, 부모 노드의 인덱스가 -1인 노드를 루트 노드로 지정한 후 함수를 시작한다. for문을 돌려 parent 값이 기준 노드 인덱스와 같은 경우 자식이라고 판단했다.

• 코드

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

public class Main {
	static int N, delN; // 노드 개수, 지울 노드
	static int rootN; // 루트노드
	static int parent[]; // 부모 배열
	static boolean isVisited[]; // 방문 여부
	static int cnt; // 리프노드 개수
	
	static void findLeaf(int node) {
		isVisited[node] = true; // 방문 체크
		
		boolean isLeaf = true;
		for (int i=0; i<N; i++) {
			if (isVisited[i] == false && parent[i] == node) { // 자식 노드가 있다면
				isLeaf = false; // 리프 노드 X
				findLeaf(i); // 자식 노드 방문
			}
		}
		if (isLeaf == true) { // 리프노드라면
			cnt++; 
			return; // 재귀 종료
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		// 첫번째줄 입력
		N = Integer.parseInt(st.nextToken());
		
		// 초기화
		parent = new int[N];
		isVisited = new boolean[N];
		rootN = -1;
		
		// 두번째줄 입력
		st = new StringTokenizer(bf.readLine());
		for(int i=0; i<N; i++) {
			parent[i] = Integer.parseInt(st.nextToken());
			if (parent[i]==-1) rootN = i;
		}
		
		// 세번째줄 입력
		st = new StringTokenizer(bf.readLine());
		delN = Integer.parseInt(st.nextToken());
		isVisited[delN] = true; // 지운 노드는 방문처리해서 그 아래로 탐색하지 않게 함
		
		if (delN!=rootN) findLeaf(rootN); // 지운 노드가 루트 노드라면 cnt = 0
		System.out.println(cnt);
	}

}

---

• 풀이 2 - ArrayList 사용

위의 코드는 함수를 실행시킬 때마다 parent배열의 for문을 전부 돌려야 한다. 물론 본 문제에서는 N이 50 이하이기 때문에 큰 차이가 나지는 않지만, N이 커질 경우 시간 효율이 떨어질 수 있다. 미리 트리의 자식을 담아둔 List를 만들어둔다면 함수를 실행시킬 때 자식 노드만 돌면 되므로 N 길이만큼 for문을 돌리지 않을 수 있다.

• 코드

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

public class Main {
	static int N, delN;
	static int rootN;
	static int parent[];
	static ArrayList<Integer> tree[];
	static int cnt;
	
	static void findLeaf(int node) {
		boolean isLeaf = true;
		for (int child : tree[node]) { // 자식 노드 탐색
			if (child!=delN) {  // 지울 노드가 아니라면
				isLeaf = false; // 리프 노드 X
				findLeaf(child); // 자식 노드 방문
			}
		}
		if (isLeaf == true) { // 리프노드라면
			cnt++; 
			return; // 재귀 종료
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		// 첫번째줄 입력
		N = Integer.parseInt(st.nextToken());
		
		// 초기화
		parent = new int[N];
		rootN = -1;
		tree = new ArrayList[N];
		for(int i=0; i<N; i++) tree[i] = new ArrayList<>();
		
		// 두번째줄 입력
		st = new StringTokenizer(bf.readLine());
		for(int i=0; i<N; i++) {
			int parent = Integer.parseInt(st.nextToken());
			if (parent==-1) rootN = i; // 루트노드 저장
			else tree[parent].add(i); // 리스트에 자식 노드 저장 
		}
		
		// 세번째줄 입력
		st = new StringTokenizer(bf.readLine());
		delN = Integer.parseInt(st.nextToken()); // 지울 노드
		
		if (delN!=rootN) findLeaf(rootN); // 지운 노드가 루트 노드라면 cnt = 0
		System.out.println(cnt);
	}

}