백준 11725: 트리의 부모 찾기
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제를 해결하기 위해서 사용할 것
✅트리 데이터를 저장할 인접 리스트 visited
✅ 방문 기록 저장 배열 tree
✅ 부모 노드 저장 정답 배열 parent
import java.io.*;
import java.util.*;
//무엇이 필요한가
//트리 데이터를 저장할 인접 리스트
//방문 기록 저장 배열
//부모 노드 저장 정답 배열
public class tmp {
static int n;
static boolean[] visited;
static ArrayList<Integer> tree[];
static int parent[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
visited = new boolean[n+1];
tree = new ArrayList[n+1];
parent = new int[n+1];
//tree 인접 리스트에 n-1개의 트리 데이터 저장
for(int i = 0; i < tree.length; i++) {
tree[i] = new ArrayList<>();
}
//데이터 추가해주자
for(int i = 1; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int num1 = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
tree[num1].add(num2);
tree[num2].add(num1);
}
DFS(1); //1부터 DFS 탐색을 시작하자
for(int i = 2; i <= n; i++) {
System.out.println(parent[i]);
}
}
static void DFS(int node) {
visited[node] = true; //방문한 노드는 true로 바꾸어 주자
for(int n: tree[node]) { //현재 위치한 노드와 인접한 노드를 탐색한다
if(!visited[n]) { //방문하지 않은 노드가 있으면
parent[n] = node; //부모 노드를 저장
DFS(n);
}
}
}
}
백준 1068: 트리: 리프 노드 찾기
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
리프 노드란: 자식 개수가 0인 노드
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성
리프 노드를 삭제하는 방법 = 탐색 알고리즘 수행할 때나 제거하는 노드가 나왔을 때 탐색을 종료
import java.io.*;
import java.util.*;
public class Main{
static int n;
static int root;
static int delete;
static int count;
static boolean[] visited;
static ArrayList<Integer> tree[];
static int parent[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
visited = new boolean[n+1];
tree = new ArrayList[n+1];
for(int i = 0; i < tree.length; i++) {
tree[i] = new ArrayList<>();
}
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
int num = Integer.parseInt(st.nextToken());
if(num != -1) {
tree[i].add(num);
tree[num].add(i);
}
else
root = i;
}
delete = Integer.parseInt(br.readLine());
if(delete == root)
System.out.println(0);
else {
DFS(root);
System.out.println(count);
}
}
static void DFS(int node) {
visited[node] = true; //방문한 노드는 true로 바꾸어 주자
int child = 0; // 리프 노드는 자식 개수가 0이므로 자식 노드 개수 저장하는 child 변수
for(int n: tree[node]) { //현재 위치한 노드와 인접한 노드를 탐색한다
//방문하지 않고 삭제할 노드가 아니라면.
//즉 아예 탐색을 해버리지 않는 것으로 '삭제'라는 작업을 구현
if(!visited[n] && n != delete) {
child++; //탐색할 자식이 있으니 +1
DFS(n);
}
}
if(child == 0)
count++; //자식 노드가 0이면 리프노드로
}
}
'Algorithms > study log' 카테고리의 다른 글
[Greedy] 백준 2141 우체국 (0) | 2024.03.19 |
---|---|
[Greedy] 연속되는 조건이 있는 문제 (1) | 2024.03.17 |
[java] 큐 / 우선순위 큐 / 힙 (0) | 2024.02.23 |
[java] 플로이드-워셜 알고리즘 (0) | 2024.02.06 |
[java] 벨만포드 알고리즘 (0) | 2024.02.06 |