[BOJ 1068] 트리 (Java, DFS)알고리즘/트리2023. 6. 26. 21:00
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/1068
문제 풀이
- 인접 리스트로 트리 정의
- 제거할 노드(REMOVE_NODE)를 인접 리스트 순회하면서 제거
- LEAF 노드 배열 값을 갱신하며 DFS 탐색
- 최종적으로 ROOT 노드의 있는 값을 출력하면 됨
- 시간 복잡도 : O(N) , (N <= 50)
제출 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, REMOVE_NODE, ROOT;
static List<Integer>[] adj;
static int[] LEAF;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
LEAF = new int[N];
adj = new ArrayList[N];
for(int i = 0; i < N; i++) adj[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
int parent = Integer.parseInt(st.nextToken());
if(parent == -1) {
ROOT = i;
continue;
}
adj[parent].add(i);
}
REMOVE_NODE = Integer.parseInt(br.readLine());
}
static void dfs(int node) {
if(adj[node].isEmpty()) {
LEAF[node] = 1;
return;
}
for(int child : adj[node]) {
dfs(child);
LEAF[node] += LEAF[child];
}
}
static void pro() {
for(int i = 0; i < N; i++) {
if(adj[i].contains(REMOVE_NODE)) {
adj[i].remove(adj[i].indexOf(REMOVE_NODE));
}
}
if(ROOT != REMOVE_NODE) dfs(ROOT);
System.out.println(LEAF[ROOT]);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
반응형
'알고리즘 > 트리' 카테고리의 다른 글
[BOJ1167] 트리의 지름 (트리) (0) | 2023.09.07 |
---|---|
[BOJ 14267] 회사 문화1 (Java, DFS, Tree) (0) | 2023.06.26 |
[BOJ 9489] 사촌 (Java, 트리) (0) | 2023.06.26 |
[BOJ 3584] 가장 가까운 공통 조상 (Java, DFS, LCA) (0) | 2023.06.26 |
[BOJ 20364] 부동산 다툼 (Java, Tree) (0) | 2023.06.26 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!