[백준 1068] 트리

😊문제

백준 1068 - 트리

😊 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N; // 노드 개수
	static int D; // 삭제할 노드 번호
	static int rootNode;
	static int cnt;
	static ArrayList<Integer> tree[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();

		tree = new ArrayList[N];

		for (int i = 0; i < tree.length; i++) {
			tree[i] = new ArrayList<>();
		}

		for (int i = 0; i < N; i++) {
			int value = sc.nextInt();
			if (value == -1) {
				rootNode = i;
			} else {
				tree[value].add(i);
			}
		}

		D = sc.nextInt(); // 지울 노드
		// 지울노드 삭제
		for (int i = 0; i < N; i++) {
			tree[i].remove(Integer.valueOf(D));
		}

		dfs(rootNode);
		System.out.println(cnt);
	}

	static void dfs(int node) {
		if (node == D) {
			return;
		}
		if (tree[node].size() == 0) {
			cnt++;
		}
		for (int nextNode : tree[node]) {
			dfs(nextNode);

		}

	}

}

😊 풀이

Main()

1. 가장 먼저 루트 노드가 없다면 -1이 주어지기 때문에
   루트 노드를 -1로 가정하고 초기화 해주었다.

2. 각 노드의 번호를 1,2,3 순으로 가정하고
   입력받은 값의 노드에 해당 값들을 넣어주었다.

3. 0번 노드부터 N번 노드까지 탐색 중,
   해당 노드에 지우고자 하는 노드 번호를 삭제

dfs()

1. 노드가 지우고자 하는 번호라면 탐색할 이유가 없기 때문에 return
2. 노드 탐색 중 해당 노드의 사이즈가 0이라면
   즉, 해당 노드에 자식노드가 없다면 리프노드라는 것이기 때문에 리프노드 개수를 출력하는 변수에 +1

🍪 내가 만든 쿠키

안봐도 그만^^

트리를 처음 접했을 때 해당 트리의 구조를 어떻게 배열에 넣어주는 것인지,
어떻게 알아서 부모노드와 자식노드를 구별해주는 것인지 도통 이해가 되지 않았다.😢
이럴 때는 수도없이 손수 손으로 써보는게 인지 상정...
하나씩 손으로 써보고 출력해보며 이해했더니
이제는 어느정도 갈피가 잡힌 것 같다.

알고리즘 문제에 다양한 테스트케이스가 많은데
어느 문제가 나오더라도 유도리 있게 구조를 그려나가는 내가 되었으면 좋겠다.

많은 알고리즘 문제를 접하면서 생각의 한계에 매번 부딪히는 경험을 하고 있는데
한계에 부딪히는 기분이 마냥 싫지만은 않다. 성장하고 있는 기분?ㅎ
이렇게 매일 부딪혀나가면 한계를 뛰어넘을 수 있는 날이 오겠지? 부디🙏