[백준] 1068번 트리

[백준] 1068번 트리

문제 설명

 

입출력

 

문제풀이 방법

트리가 주어지고, 삭제할 노드에 연결되어 있는 노드를 모두 제거한 후 리프노드의 개수를 출력하면 된다.

 

 

1. 주어진 노드가 어떤 루트 노드와 연결되어 있는지 정보를 저장할 arr 배열 하나를 선언한다. 

 

2. 삭제할 노드 R 을 입력받은 후 delete(R) 을 통해 R에 연결되어 있는 노드를 모두 삭제한다. 

   - 삭제가 된 노드인지를 판별하기 위해 boolean값의 node 배열을 사용했다. 

   - 삭제가 된 노드면 node[i]의 값을 true로 바꾸게 된다.

   - 삭제를 하는 방법은 BFS방법을 통해 연결된 것을 모두 지우도록 했다. 

 

3. 삭제가 끝나면 리프노드를 찾아야 한다. 

   - 삭제되어진 노드는 제외하고 ( 즉, node가 true인 것은 제외 ) 루트 노드도 제외해야한다.

   - 그 중, 루트 노드의 정보를 HashSet에 저장한다. 

      --> 그 이유는 해당 노드의 루트라 함은 그 루트 노드는 자식을 하나이상 가지고 있는 것이 되기 때문에 리프노드가 될 수 없다. 

 

4. 모든 과정은 끝났고, 이제 리프 노드의 개수를 구해주면 된다. 

   - 삭제된 노드를 제외하고 자식이 있는 노드를 제외한 수를 계산하면 된다. 

 

 

후기

- 트리라고 미리 겁먹을 필요 없다!

- 사실 크기가 크기 않기 때문에 어렵지 않게 풀었던 것 같다.

 

 

 

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Tree_1068 {

    static int N;
    static int[] arr;
    static boolean[] node;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        node = new boolean[N];
        HashSet<Integer> set = new HashSet<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            node[i] = false;
        }

        int R = Integer.parseInt(br.readLine());

        delete(R);

        for(int i=0; i<N; i++) {
            if(!node[i] && arr[i] >= 0) {
                set.add(arr[i]);
            }
        }

        int cnt = 0;
        for(int i=0; i<N; i++) {
            if(!node[i] && !set.contains(i)) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    public static void delete(int start) {
        node[start] = true;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int index = queue.poll();

            for(int i=0; i<N; i++) {
                if(index == arr[i] && !node[i]) {
                    node[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

 

 

 

 

문제 링크

www.acmicpc.net/problem/1068

1068번: 트리