rose_brown

[백준] 1068번_트리 본문

코딩/백준

[백준] 1068번_트리

rose_brown 2024. 11. 5. 16:39

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)

풀이

  1. N - 노드개수, tree - 그래프 데이터 저장 인접 리스트p - 입력 데이터 저장
  2. visited - 방문 기록 저장, answer - 리프 노드 개수 저장
  3. for N만큼 반복
    1. if 루트 노드가 아님 → tree 인접 리스트에 트리 데이터 저장
    2. else → 루트 노드 값 저장
  4. DFS(현재 노드)
    1. 방문 리스트에 현재 노드 방문 기록
    2. for 연결 노드 탐색
      1. if 현재 노드의 연결 노드 중 방문하지 않은 노드이고 삭제 노드가 아닐 때
        1. 자식 노드 개수 증가
        2. DFS 실행(다음 탐색 노드)
        3. if 자식 노드 개수가 0 → answer값 1 증가
  5. delNode - 삭제노드 값 저장
  6. if 살제 노드값이 root와 같으면 → 모두 삭제되므로 0을 출력하고 프로세스 끝냄
  7. 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