Notice
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- Level3
- sql
- python
- 알고리즘
- 구현
- dp
- 백준
- KT 에이블스쿨
- AIVLE
- 딕셔너리
- Level1
- 패스트캠퍼스
- kt에이블스쿨5기
- 실버
- 그래프
- 프로그래머스
- spring
- 오블완
- Java
- 파이썬
- 정렬
- 트리
- 골드
- dfs
- KT에이블스쿨
- 티스토리챌린지
- BFS
- AI트랙
- Level2
- join
Archives
- Today
- Total
rose_brown
[백준] 1068번_트리 본문
1. 문제
https://www.acmicpc.net/problem/1068
2. 코드
python
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
tree = [[] for _ in range(N+1)]
visited = [False] * (N+1)
answer = 0
p = list(map(int, input().split()))
del_num = int(input())
for i in range(N):
if p[i] != -1:
tree[i].append(p[i])
tree[p[i]].append(i)
else:
root = i
def DFS(num):
global answer
visited[num] = True
cNode = 0
for i in tree[num]:
if not visited[i] and i != del_num:
cNode += 1
DFS(i)
if cNode == 0:
answer += 1
if del_num == root:
print(0)
else:
DFS(root)
print(answer)
풀이
- N - 노드개수, tree - 그래프 데이터 저장 인접 리스트p - 입력 데이터 저장
- visited - 방문 기록 저장, answer - 리프 노드 개수 저장
- for N만큼 반복
- if 루트 노드가 아님 → tree 인접 리스트에 트리 데이터 저장
- else → 루트 노드 값 저장
- DFS(현재 노드)
- 방문 리스트에 현재 노드 방문 기록
- for 연결 노드 탐색
- if 현재 노드의 연결 노드 중 방문하지 않은 노드이고 삭제 노드가 아닐 때
- 자식 노드 개수 증가
- DFS 실행(다음 탐색 노드)
- if 자식 노드 개수가 0 → answer값 1 증가
- if 현재 노드의 연결 노드 중 방문하지 않은 노드이고 삭제 노드가 아닐 때
- delNode - 삭제노드 값 저장
- if 살제 노드값이 root와 같으면 → 모두 삭제되므로 0을 출력하고 프로세스 끝냄
- else → DFS(root) answer 출력
Java
import java.io.*;
import java.util.*;
public class Main {
static List<Integer>[] tree;
static boolean[] visited;
static int answer = 0;
static int delNum;
static int root;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
tree = new ArrayList[N];
visited = new boolean[N];
for (int i = 0; i < N; i++) {
tree[i] = new ArrayList<>();
}
int[] p = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
p[i] = Integer.parseInt(st.nextToken());
if (p[i] != -1){
tree[i].add(p[i]);
tree[p[i]].add(i);
}
else{
root = i;
}
}
delNum = Integer.parseInt(br.readLine());
if (delNum == root){
System.out.println(0);
}
else {
DFS(root);
System.out.println(answer);
}
}
static void DFS(int num){
visited[num] = true;
int cNode = 0;
for (int i:tree[num]){
if (!visited[i] && i != delNum){
cNode++;
DFS(i);
}
}
if (cNode == 0){
answer++;
}
}
}
3. 메모
- tree의 기본사용
- DFS를 통해 노드 찾음
- 이때 리프노드가 언제인지 이해해야함
'코딩 > 백준' 카테고리의 다른 글
[백준] 1991번_트리 순회 (0) | 2024.11.07 |
---|---|
[백준] 14425번_문자열 집합 (0) | 2024.11.05 |
[백준] 11725번_트리의 부모 찾기 (0) | 2024.11.05 |
[백준] 1414번_불우이웃돕기 (0) | 2024.11.04 |
[백준] 17472번_다리 만들기 2 (0) | 2024.11.04 |