백준(1068번) - 트리
문제 출처: https://www.acmicpc.net/problem/1068
문제
- 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
-
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
-
예를 들어, 다음과 같은 트리가 있다고 하자.
- 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.
- 이제 리프 노드의 개수는 1개이다.
- BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static class Node {
int vertex;
Node next;
public Node(int vertex, Node next) {
this.vertex = vertex;
this.next = next;
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine()); // 노드의 개수
Node[] adjList = new Node[N];
int index = 0;
int root = 0;
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
while (tokenizer.hasMoreTokens()) {
int curr = Integer.parseInt(tokenizer.nextToken());
if (curr == -1) {
root = index++;
continue;
}
adjList[curr] = new Node(index++, adjList[curr]);
}
System.out.println(bfs(adjList, root, Integer.parseInt(reader.readLine())));
}
private static int bfs(Node[] adjList, int root, int remove) {
Queue<Integer> queue = new ArrayDeque<>();
if (root == remove) return 0;
queue.offer(root);
int result = 0;
while (!queue.isEmpty()) {
int curr = queue.poll();
boolean flag = false;
for (Node node = adjList[curr]; node != null; node = node.next) {
if (node.vertex == remove) continue;
flag = true;
queue.offer(node.vertex);
}
if (!flag) result++;
}
return result;
}
}
- DFS + ArrayList
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int result;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine()); // 노드의 개수
List<Integer>[] adjList = new List[N];
for (int i = 0; i < N; i++) {
adjList[i] = new ArrayList<>();
}
int index = 0;
int root = 0;
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
while (tokenizer.hasMoreTokens()) {
int curr = Integer.parseInt(tokenizer.nextToken());
if (curr == -1) {
root = index++;
continue;
}
adjList[curr].add(index++);
}
int remove = Integer.parseInt(reader.readLine());
if (root != remove) dfs(adjList, root, remove);
System.out.println(result);
}
private static void dfs(List<Integer>[] adjList, int curr, int remove) {
boolean flag = false;
for (int n : adjList[curr]) {
if (n == remove) continue;
flag = true;
dfs(adjList, n, remove);
}
if (!flag) result++;
}
}
- 인접 리스트와 BFS를 활용하여 비교적 수월하게 풀 수 있는 문제였다.
- 굳이 BFS를 안쓰고 DFS를 사용해도 풀 수 있을 것 같다.
- 이 문제의 관건은 리프 노드의 개수를 세는 것인데, 처음 인접 리스트에 추가할 때 일부러 부모 → 자식으로 향하는 단방향 리스트로 만들었다. 그래서 특정 노드를 지울 때 굳이 양방향을 생각하지 않고 바로 큐에 삽입을 건너뛰는 것으로 해결할 수 있었다.
Author And Source
이 문제에 관하여(백준(1068번) - 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ghc1124/백준1068번-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)