문제 설명
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
접근 방법
문제의 입력값으로 최초 n개의 각각의 노드별로 부모 노드가 주어지는데, 이를 해쉬 맵 자료구조에 저장합니다. 이때 루트 노드는 부모 노드가 없으므로 루트 노드만 따로 별도의 변수(rootNodeIndex)에 저장해주도록 합니다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Map<Integer, Integer> parentByNode = new HashMap<>();
int rootNodeIndex = 0, parentIndex;
for (int i = 0; i < n; i++) {
parentIndex = Integer.parseInt(st.nextToken());
if (parentIndex == -1) {
rootNodeIndex = i;
} else {
parentByNode.put(i, parentIndex);
}
}
이후 앞서 저장한 루트 노드 인덱스를 통해 '별도로 선언한 트리 클래스'의 인스턴스를 생성해줍니다. 아울러 트리 클래스는 마찬가지로 별도로 선언한 노드 클래스로 구성되게 됩니다.
static class Tree {
Node root;
public Tree(Node root) {
this.root = root;
}
// ...
}
static class Node {
int index;
List<Node> children;
public Node(int index) {
this.index = index;
children = new ArrayList<>();
}
public void add(Node node) {
children.add(node);
}
}
// ...
Tree tree = new Tree(new Node(rootNodeIndex));
그 다음에는 루트 노드를 제외한 나머지 노드별 부모 노드를 저장했던 해쉬 맵을 통해 트리 구조를 완성해가도록 합니다. 이때 트리 클래스에 별도로 구현한 너비 우선 탐색 방식으로 부모 노드를 찾도록 했고 부모 노드가 없는 경우도 있을 수 있으므로 큐 자료구조를 이용해 부모 노드가 없는 경우 큐의 맨 뒤로 보내는 식으로 부모 노드가 있는 노드를 우선적으로 처리해주도록 합니다.
static class Tree {
// ...
public Node search(int index) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
if (root.index == index) {
return root;
}
while (!queue.isEmpty()) {
Node node = queue.poll();
for (Node child : node.children) {
if (child.index == index) {
return child;
}
if (child.children.size() > 0) {
queue.add(child);
}
}
}
return null;
}
// ...
}
// ...
Queue<Integer> queue = new LinkedList<>(parentByNode.keySet());
while (!queue.isEmpty()) {
Integer nodeIndex = queue.poll();
Node parentNode = tree.search(parentByNode.get(nodeIndex));
if (parentNode != null) {
parentNode.add(new Node(nodeIndex));
} else {
queue.add(nodeIndex);
}
}
이제 삭제할 노드의 부모 노드를 찾은 다음에 부모 노드가 참조하고 있는 해당 자식 노드를 삭제시킵니다. 이때 삭제하려는 노드가 루트 노드인 경우 리프 노드는 없게 되므로 별도로 분기하여 0을 출력해주도록 합니다.
int deleteIndex = Integer.parseInt(br.readLine());
if (deleteIndex == rootNodeIndex) {
System.out.println(0);
return;
}
Node node = tree.search(parentByNode.get(deleteIndex));
for (Node child : node.children) {
if (child.index == deleteIndex) {
node.children.remove(child);
break;
}
}
마지막으로 현재 트리 구조 상의 리프 노드 개수를 구해주도록 합니다. 이때 탐색 방식은 동일하게 너비 우선 탐색을 이용했습니다. 이때 주의할 점으로는 루트 노드의 자식 노드가 없는 경우에는 루트 노드 자체가 리프 노드가 되므로 1을 반환해주도록 처리해야합니다.
static class Tree {
// ...
public int getCountOfLeafNodes() {
if (root.children.size() == 0) {
return 1;
}
int result = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
for (Node child : node.children) {
if (child.children.size() == 0) {
result++;
} else {
queue.add(child);
}
}
}
return result;
}
// ...
}
// ...
System.out.println(tree.getCountOfLeafNodes());
전체 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
static class Tree {
Node root;
public Tree(Node root) {
this.root = root;
}
public Node search(int index) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
if (root.index == index) {
return root;
}
while (!queue.isEmpty()) {
Node node = queue.poll();
for (Node child : node.children) {
if (child.index == index) {
return child;
}
if (child.children.size() > 0) {
queue.add(child);
}
}
}
return null;
}
public int getCountOfLeafNodes() {
if (root.children.size() == 0) {
return 1;
}
int result = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
for (Node child : node.children) {
if (child.children.size() == 0) {
result++;
} else {
queue.add(child);
}
}
}
return result;
}
}
static class Node {
int index;
List<Node> children;
public Node(int index) {
this.index = index;
children = new ArrayList<>();
}
public void add(Node node) {
children.add(node);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Map<Integer, Integer> parentByNode = new HashMap<>();
int rootNodeIndex = 0, parentIndex;
for (int i = 0; i < n; i++) {
parentIndex = Integer.parseInt(st.nextToken());
if (parentIndex == -1) {
rootNodeIndex = i;
} else {
parentByNode.put(i, parentIndex);
}
}
Tree tree = new Tree(new Node(rootNodeIndex));
Queue<Integer> queue = new LinkedList<>(parentByNode.keySet());
while (!queue.isEmpty()) {
Integer nodeIndex = queue.poll();
Node parentNode = tree.search(parentByNode.get(nodeIndex));
if (parentNode != null) {
parentNode.add(new Node(nodeIndex));
} else {
queue.add(nodeIndex);
}
}
int deleteIndex = Integer.parseInt(br.readLine());
if (deleteIndex == rootNodeIndex) {
System.out.println(0);
return;
}
Node node = tree.search(parentByNode.get(deleteIndex));
for (Node child : node.children) {
if (child.index == deleteIndex) {
node.children.remove(child);
break;
}
}
System.out.println(tree.getCountOfLeafNodes());
}
}
참고 자료
'Algorithm > BOJ' 카테고리의 다른 글
| [백준 - 1011] Fly me to the Alpha Centauri - Java (0) | 2022.09.06 |
|---|---|
| [백준 - 9019] DSLR - Java (0) | 2022.08.20 |
| [백준 - 25332] 수들의 합 8 - Java (0) | 2022.08.11 |
| [백준 - 25331] Drop 7 - Java (2) | 2022.08.08 |
| [백준 - 14503] 로봇 청소기 - Java (0) | 2022.08.03 |