Do it! 알고리즘 코딩 테스트 (67번 ~ 68번)

67번 트리의 부모 찾기

---

내가 떠올린 풀이 해설

인접 리스트 자료구조를 사용하면 간편하게 데이터를 저장할 수 있다. 트리의 루트가 1이라고 지정돼 있기 때문에 1번 노드부터 DFS로 탐색하면서 부모 노드를 찾아 주면 문제를 쉽게 풀 수 있다. 출력은 정답 배열의 2번 인덱스부터 값을 차례대로 출력한다.

---

정확한 풀이

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

public class Baek11725 {
	static ArrayList<Integer>[] arr;
	static int[] answer;
	static boolean[] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n + 1];
		visit = new boolean[n + 1];
		answer = new int[n + 1];
		
		for(int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i = 1; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			arr[s].add(e);
			arr[e].add(s);
		}
		DFS(1);
		for(int i = 2; i <= n; i++) {
			System.out.println(answer[i]);
		}
	}
	private static void DFS(int i) {
		visit[i] = true;
		for(int k : arr[i]) {
			if(!visit[k]) {
				answer[k] = i;
				DFS(k);
			}
		}
	}
}

---

68번 트리

---

내가 떠올린 풀이 해설

이 문제의 핵심은 리프 노드를 어떻게 제거하는지 이다. 리프 노드를 탐색하는 탐색 알고리즘을 수행할 때나 제거하는 노드가 나왔을 때 탐색을 종료하는 아이디어를 적용하면 실제 리프 노드를 제거하는 효과를 낼 수 있다. 인접 리스트로 트리 데이터를 구현한다. DFS를 탐색하면서 리프 노드의 개수를 센다. 제거 대상 노드를 만났을 때 그 아래 자식 노드들과 관련된 탐색은 중지한다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1068 {
	static ArrayList<Integer>[] arr;
	static boolean[] visit;
	static int r;
	static int answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n];
		visit = new boolean[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = new ArrayList<>();
		}
		int root = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			int s = Integer.parseInt(st.nextToken());
			if(s != -1) {
				arr[s].add(i);
				arr[i].add(s);
			}
			else {
				root = i;
			}
		}
		r = Integer.parseInt(br.readLine());
		if(r == root) {
			System.out.println(0);
		}
		else {
			DFS(root);
			System.out.println(answer);
		}
	}
	private static void DFS(int root) {
		visit[root] = true;
		int c = 0;
		for(int v : arr[root]) {
			if(!visit[v] && v != r) { // 삭제 노드가 아닐 떼도 탐색 중지 
				c++;
				DFS(v);
			}
		}
		if(c == 0) {
			answer++; // 자식 노드가 아닐 때 리프 노드로 간주하고 정답값 증가 
		}
	}
}

---

오늘의 회고

오늘은 트리와 관련된 문제 2문제를 풀었습니다. 알고리즘 개념에 대해 복습하는 시간을 가지면서 초반보다 문제를 푸는 개수가 많이 줄어들어 시간도 부족하고 알고리즘을 끝낼 수 있을까란 조바심도 들지만 천천히 조바심 가지지 않고 완전히 내 것으로 만들면서 나아가겠습니다.