[알고리즘] 백준 > #1068. 트리
문제링크
풀이방법
이름처럼 트리를 이용하면 해결할 수 있는 문제다! 일단 각 노드에 자식 노드를 저장한다. 입력된 잘린 노드(removedNode)가 자식이라면 그 자식을 children 리스트에서 제거 한 뒤 완전탐색(BFS)을 통해 리프노드를 카운트했다!
간과한 점들 때문에 두번 틀리고 문제를 해결할 수 있었다. 간과한 점들은 다음과 같다.
- 이진트리가 아니다 (설명 어디에도 이진트리란 말은 없다)
- 초기에 leaf 노드가 아니더라도 자식이 잘려나가 leaf 노드가 될 수 있다.
이진 트리가 아니기 때문에 children을 LinkedList 자료구조로 관리했고 완전탐색 시 모든 노드에 대해 leaf 노드가 아닌지 확인(children.isEmpty())을 진행했다.
코드
import java.util.*;
public class BOJ1068 {
private static Node[] tree;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
tree = new Node[n];
int[] parentArray = new int[n];
for (int i = 0; i < n; i++) tree[i] = new Node();
int rootNode = 0;
for (int i = 0; i < n; i++) {
int parent = sc.nextInt();
if (parent == -1) rootNode = i;
else tree[parent].children.add(i);
parentArray[i] = parent;
}
int count = 0;
Integer removedNode = sc.nextInt();
if (removedNode == rootNode) count = 0;
else {
tree[parentArray[removedNode]].children.remove(removedNode);
Queue<Integer> q = new LinkedList<>();
q.add(rootNode);
while (!q.isEmpty()) {
int head = q.poll();
if (tree[head].children.isEmpty()) count++;
else q.addAll(tree[head].children);
}
}
System.out.print(count);
}
}
class Node {
public LinkedList<Integer> children;
public Node() {
children = new LinkedList<>();
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 > #1068. 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cchloe2311/알고리즘-백준-1068.-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)