(JAVA) 백준 1068번 : 트리

https://www.acmicpc.net/problem/1068

1068번: 트리

 

1068, 트리

📌 난이도 : Gold 5

📌 알고리즘 : DFS

📌 자료구조 : 트리

 

이번 문제는 DFS 와 트리 구조를 사용하여 문제풀이를 진행했다.

 

💻

📚 Process

초기화 및 선언

: 노드의 개수만큼 ArrayList<>[] adj 를 생성해준다. 이는 부모 노드에 연결된 자식 노드들을 표기하기 위함이다.

N개 만큼 ArrayList를 선언해주고 시작 노드와 삭제할 노드를 차례로 입력받는다. + 트리연결

public static void input() throws IOException {
    N = Integer.parseInt(br.readLine());
    adj = new ArrayList[N];
    for(int i=0; i<N; i++) adj[i] = new ArrayList<>();

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    for(int i=0; i<N; i++) {
        int t = Integer.parseInt(st.nextToken());
        // 시작 기점
        if(t == -1) {
            S = i;
            continue;
        }
        // 트리 연결
        adj[t].add(i);
    }

    X = Integer.parseInt(br.readLine());
}

 

DFS

: DFS 를 호출하기 전에 그래프상 가장 위쪽에 위치한 부모 노드와 삭제할 노드가 같다면 0을 출력하고 탐색을 종료한다.

X번 노드를 삭제한다. 이것은 재귀함수를 통해 해당 노드의 자식 노드들을 모두 조회하고 삭제하는 과정이다.

이 과정을 마치고 나면 DFS 를 호출한다. 리프 노드는 i번째 노드 즉, adj[i] 에 자식 노드들이 없음을 의미한다.

adj[i].size() 가 0인 경우 리프노드임을 확인하고 카운트 + 1 을 해주고 탐색을 이어서 진행한다.

public static void pro() throws IOException {
    if(X == S) {
        System.out.println(0);
        return;
    }
    // X번 노드 삭제
    removeNode(X);
    // 탐색
    System.out.println(BFS(S));
}

public static void removeNode(int node) {
    // [재귀] 해당 노드, 자식노 드 모두 조회
    if(adj[node].size()>0) {
        int size = adj[node].size();
        while(size-- > 0) {
            int child = adj[node].get(size);
            removeNode(child);
        }   
    }

    // 해당 노드, 자식 노드 모두 삭제 
    for(int i=0; i<N; i++) {
        if(adj[i].contains(node)) {
            for(int j=0; j<adj[i].size(); j++) {
                if(adj[i].get(j) == node) {
                    adj[i].remove(j);
                }
            }
        }
    }
}

public static int BFS(int start) {
    Queue<Integer> que = new LinkedList<>();
    que.add(start);

    int cnt = 0;

    while(!que.isEmpty()) {
        int x = que.poll();

        // 리프노드
        if(adj[x].size() == 0) {
            cnt++;
            continue;
        }

        for(int k : adj[x]) {
            que.add(k);
        }
    }

    return cnt;
}

 

✅ 전체 코드

: 트리 구조에 대한 개념과 부모 노드를 삭제할 때 자식 노드들을 삭제하는 로직을 직접 이해하고 구현할 수 있는 좋은 문제였던 것 같다.

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static ArrayList<Integer>[] adj;
    static int N,X,S;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        adj = new ArrayList[N];
        for(int i=0; i<N; i++) adj[i] = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++) {
            int t = Integer.parseInt(st.nextToken());
            // 시작 기점
            if(t == -1) {
                S = i;
                continue;
            }
            // 트리 연결
            adj[t].add(i);
        }

        X = Integer.parseInt(br.readLine());
    }

    public static void pro() throws IOException {
        if(X == S) {
            System.out.println(0);
            return;
        }
        // X번 노드 삭제
        removeNode(X);
        // 탐색
        System.out.println(BFS(S));
    }

    public static void removeNode(int node) {
        // [재귀] 해당 노드, 자식노 드 모두 조회
        if(adj[node].size()>0) {
            int size = adj[node].size();
            while(size-- > 0) {
                int child = adj[node].get(size);
                removeNode(child);
            }   
        }

        // 해당 노드, 자식 노드 모두 삭제 
		for(int i=0; i<N; i++) {
			if(adj[i].contains(node)) {
				for(int j=0; j<adj[i].size(); j++) {
					if(adj[i].get(j) == node) {
						adj[i].remove(j);
					}
				}
			}
		}
    }

    public static int BFS(int start) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);

        int cnt = 0;

        while(!que.isEmpty()) {
            int x = que.poll();
            
            // 리프노드
            if(adj[x].size() == 0) {
                cnt++;
                continue;
            }

            for(int k : adj[x]) {
                que.add(k);
            }
        }
        
        return cnt;
    }
}