[JAVA] 백준 1068 트리

 

 

 

 

1068번: 트리

문제

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

풀이

해당 문제는 트리가 주어졌을 때 노드를 하나 지우고 해당 노드가 지워진 상태에서의 리프 노드의 개수를 구하는 문제였습니다.

저는 문제를 해결하기 위해서 해당 삭제되는 노드를 탐색하지 않고 DFS, BFS를 진행함으로써 삭제된 것 처럼 풀었습니다.

📌 입력

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            int a = Integer.parseInt(st.nextToken());

            if(a != -1){
                A[i].add(a);
                A[a].add(i);
            }else{
                root = i;
            }
        }

만약 입력받은 값이 -1이라면 root 노드라는 의미이기 때문에 root 변수에 담아주고 -1이 아니라면 양방향 인접 리스트 그래프로 만들어 주었습니다.

📌 DFS

public static void DFS(int a){
        if(a == D) return;

        V[a] = true;
        int count = 0;
        for(int x : A[a]){
            if(!V[x] && x != D){
                count++;
                DFS(x);
            }
        }
        if(count == 0) answer++;
    }

만약 a == D라면 (루트가 D인 경우) 바로 종료하였습니다.

재귀적으로 돌면서 DFS를 진행하였고 forEach 문에 있는 if문을 통과하는 노드가 하나도 없는 경우 정답을 체크하였습니다.

📌 BFS

    public static void BFS(int a){
        if (a == D) return;
        Queue<Integer> q = new LinkedList<>();

        q.add(a);
        V[a] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            int count = 0;
            for (int x : A[now]){
                if(!V[x] && x != D){
                    V[x] = true;
                    q.add(x);
                    count++;
                }
            }
            if(count == 0) {
                answer++;}
        }
    }

BFS도 마찬가지로 root가 D라면 바로 종료하였습니다.

BFS도 똑같이 forEach 문의 if를 통과한적이 없는 노드라면 정답에 체크해주었습니다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static ArrayList<Integer>[] A;
    static boolean[] V;
    static int D;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));

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

        V = new boolean[N];
        A = new ArrayList[N];
        for(int i=0; i<N; i++){
            A[i] = new ArrayList<>();
        }

        int root = 0;
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            int a = Integer.parseInt(st.nextToken());

            if(a != -1){
                A[i].add(a);
                A[a].add(i);
            }else{
                root = i;
            }
        }

        D = Integer.parseInt(br.readLine());
        DFS(root);
        System.out.println(answer);
    }

    public static void BFS(int a){
        if (a == D) return;
        Queue<Integer> q = new LinkedList<>();

        q.add(a);
        V[a] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            int count = 0;
            for (int x : A[now]){
                if(!V[x] && x != D){
                    V[x] = true;
                    q.add(x);
                    count++;
                }
            }
            if(count == 0) {
                answer++;}
        }
    }

    public static void DFS(int a){
        if(a == D) return;

        V[a] = true;
        int count = 0;
        for(int x : A[a]){
            if(!V[x] && x != D){
                count++;
                DFS(x);
            }
        }
        if(count == 0) answer++;
    }

}

결과

BFS

DFS

DFS와 BFS 모두 메모리나 시간에 큰 차이를 보이진 않았습니다.