[백준/JAVA] 1068번: 트리

🔺 문제

1068번: 트리

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, deleteNode, answer;
    static boolean visited[];           // 방문 저장 배열
    static ArrayList<Integer>[] tree;   // 인접 리스트
    
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        
        int N = sc.nextInt();
        visited = new boolean[N];
        
        // 인접 리스트 초기화
        tree = new ArrayList[N];
        for(int i = 0 ; i < N ; i++) {
            tree[i] = new ArrayList<>();
        }
        
        // 입력 받아 인접 리스트 채우기
        int root = 0;        
        for(int i = 0 ; i < N ; i++) {
            int p = sc.nextInt();
            
            if(p != -1) {
                tree[i].add(p);
                tree[p].add(i);
            } else {
                root = i;
            }
        }
        
        // DFS 수행 (삭제 노드 전까지)
        deleteNode = sc.nextInt();
        if(deleteNode == root) {
            sb.append(0);
        } else {
            DFS(root);
            sb.append(answer);
        }
        
        System.out.println(sb);
    }
    
    public static void DFS(int num) {
        visited[num] = true;
        int cNode = 0;  // 자식 노드 개수
        
        for(int i : tree[num]) {
            if(!visited[i] && i != deleteNode) { 
                cNode++;
                DFS(i);
            }
        }
        
        // 자식 노드 개수가 0일 때, 리프 노드로 간주
        if(cNode == 0) {
            answer++;
        }
    }
}

✅ 해결 아이디어
✔ DFS
- 삭제 노드 출현 시, 탐색 종료!
→ DFS에서 자식 노드 갯수가 0일 때 리프 노드로 간주한다.

 

---

🔺 다른 풀이들

- 인접 리스트를 사용하지 않은 흥미로운 풀이...

[백준]1068: 트리 - JAVA

 

 

- 노드 클래스를 만들고 DFS를 수행하셨다.

[백준 1068] 트리(JAVA)

 

 

 

- BFS로 푸심

[백준/자바] 1068 트리

---

💬 느낀 점

리프 노드 제거 조건만 잘 찾으면 되는 문제,,,

조건을 찾자!

 

(*리프 노드 : 자식 노드가 없는 노드)

 

1회독	2회독	3회독	4회독	5회독
V	6/28

 

 

(+ 6/28 2회독)

isLeaf : 현재 탐색 중인 노드의 자식 노드 여부를 확인하기 위한 용도로 사용..

& DFS 사용

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, root, delNode, answer;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        A = new ArrayList[N];
        for(int i = 0 ; i < N ; i++) {
            A[i] = new ArrayList<>();
        }
        visited = new boolean[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(num == -1) {
                root = i;
            } else {
                A[num].add(i);
                A[i].add(num);                
            }
        }
        
        // 삭제 노드 전까지 DFS 수행
        delNode = Integer.parseInt(br.readLine());
        if(delNode == root) {
            System.out.println(0);
        } else {
            dfs(root);
            System.out.println(answer);
        }
    }
    
    private static void dfs(int num) {
        visited[num] = true;
        boolean isLeaf = true;    // 🔔 자식 노드 여부 확인 변수 🔔
        
        for(int next : A[num]) {
            // 🔔 방문 X인 노드 & 삭제 노드가 아닐 때, 리프 노드가 아님 🔔
            if(!visited[next] && next != delNode) {
                isLeaf = false;
                dfs(next);
            }
        }
        
        if(isLeaf) answer++;
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편