백준 1068번: 트리[JAVA]

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

1068번: 트리

 

 

[정답 코드]

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

public class Main {
    static int root;
    static Node[] tree;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        tree = new Node[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            tree[i] = new Node(parent); // 노드의 번호는 i, i번 노드의 부모는 parent 인 Node를 생성
            if (parent == -1) { // parent 번호가 -1 이면 해당 노드는 루트 노드
                root = i;
            }
        }

        // 루트 노드가 아닌 경우, 해당 노드의 부모 노드를 찾아 자식노드에 자신을 추가
        for (int i = 0; i < N; i++) {
            if (root != i) { // 루트노드가 아닐경우
                int parent = tree[i].parent; // i 번 노드의 부모노드를 꺼내서
                tree[parent].addChild(i); // 부모노드의 자식에 i번 노드를 추가해줌
            }
        }

        int removeNode = Integer.parseInt(br.readLine()); // 삭제 할 노드 번호
        if (removeNode == root) { // 루트 노드를 지울경우 전부 삭제되므로 0 출력
            System.out.println(0);
        } else {
            int parent = tree[removeNode].parent; // 삭제하려는 노드의 부모 노드의 값을 꺼냄
            tree[parent].removeChild(removeNode); // 그 부모노드의 자식노드들 중 삭제하려는 노드번호를 삭제
            int leafSize = getLeafSize(root); // 리프노드의 수를 카운팅
            System.out.println(leafSize);
        }
    }

    static int getLeafSize(int index) {
        if (tree[index].isLeaf()) { // 해당 노드의 자식노드가 없다면 true 를 반환해서
            return 1; // 1 반환
        }
        int sum = 0;
        for (int i = 0; i < tree[index].getChildrenSize(); i++) {
            sum += getLeafSize(tree[index].children.get(i)); // 반복문을 재귀적으로 돌며 자식노드가 없는 노드들을 탐색
        }
        return sum;
    }
}

// 노드 클래스
class Node {
    int parent; // 해당 노드의 부모 노드
    List<Integer> children; // 자식노드들

    public Node(int parent) {
        this.parent = parent;
        this.children = new ArrayList<>(); // 자식노드들은 ArrayList 로 생성
    }

    public void addChild(int child) { // 노드의 자식들을 ArrayList.add 로 삽입
        this.children.add(child);
    }

    public void removeChild(int child) { // 노드의 자식들을 ArrayList.remove 로 삭제
        this.children.remove(Integer.valueOf(child));
    }

    public boolean isLeaf() { // 노드의 자식이 없다면 true 반환
        return this.children.isEmpty();
    }

    public int getChildrenSize() { // 노드의 자식들의 개수를 ArrayList.size() 메서드를 활용해 출력
        return this.children.size();
    }
}

 

[설명]

저번에 풀었던 노드의 심화버전이다. 그래서 저번에 풀었던 코드를 조금만 수정해 풀려고 했으나 실패해 포기해 다른분들의 코드를 찾아보며 풀어버렸다.

예제 입력 1번을 예시로 설명을 해보자면

 

1. Node클래스 배열을 선언

• 노드배열의 인덱스가 해당 노드의 밸류
  노드 클래스의 필드는 parent(부모노드번호), childrent(자식노드들을 ArrayList로 가변적으로 선언)
• tree[0] = new Node(-1)
  tree[1] = new Node(0)
  tree[2] = new Node(0)
  tree[3] = new Node(1)
  tree[4] = new Node(1)
  root = 0

2. 각 클래스들의 부모를 찾아 자기자신을 그 부모노드의 자식으로 추가함

ArrayList.add 를 사용해 추가

• i=0
  int parent = tree[0].parent = -1 // parent가  root 일 경우 if문 false
  
  i = 1
  int parent = tree[1].parent = 0
  tree[0].addChild(1);
  
  i = 2
  int parent = tree[2].parent = 0
  tree[0].addChild(2);
  
  i = 3
  int parent = tree[3].parent = 1
  tree[1].addChild(3);
  
  i = 4
  int parent = tree[4].parent = 1
  tree[1].addChild(4);

3. 삭제할 노드를 입력받아 해당 노드를 삭제함

• 삭제할 노드를 입력받고 해당 노드의 부모노드를 탐색 -> 삭제하려는 부모노드의 자식들중 삭제하려는 노드와 같은 자식을 ArrayList.remove() 메서드로 삭제
• removeNode = 2
  int parent = tree[2].parent = 0
  tree[0].removeChild(2)

4. 리프 노드를 카운팅

• 루트노드부터 시작해 모든 자식노드들을 방문하며 어떤 노드의 Children.isEmpty가 true일경우 sum 을 1씩 증가시킴
• 이 로직을 재귀적으로 반복해가며 모든 노드들을 방문함