[백준] 1068 트리(Java)

문제링크

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

문제분석

• 주어진 트리에서 노드를 하나 지운다
  • 지운 노드의 자손 노드들까지 제거된다.
• 남은 트리에서 리프 노드의 개수는?

입력

• 노드의 개수 N (1<= N <=50)
• 0 ~ N-1번 노드까지의 부모노드 번호
• 지울 노드의 번호

출력

• 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수

풀이

• 노드를 표현할 노드 클래스 선언 : 자식 리스트만을 멤버로 가지고 있다

class Node{
    ArrayList<Node> child; //자식들을 가지고 있다.
}

• 트리를 선언 후, 노드간의 관계를 연결한다.
  • 트리 선언 : ArrayList로 노드의 개수만큼 Node 클래스를 만든다.
  • 관계 연결 : 부모 노드의 child 리스트에 자식노드의 주소 저장

//트리 선언
ArrayList<Node> tree = new ArrayList<>();
for (int i = 0; i < n; i++) tree.add(new Node());

//노드간의 관계 연결
for(int i=0; i<n; i++){
	if(input[i]!=-1) tree.get(input[i]).child.add(tree.get(i));
}

• 삭제 노드의 부모에서 삭제노드를 제거한다.
  • 예외처리 : 루트노드를 삭제하는 경우 리스트의 -1 index에 접근하게 된다.

		if(deleteNode!=root) { //삭제 노드가 root 노드가 아닐 경우
            // 부모노드에서 삭제 노드를 제거한다.
            tree.get(input[deleteNode]).child.remove(tree.get(deleteNode));
            DFS(tree.get(root)); //DFS로 리프노드 개수를 센다.
        }else{ // 삭제 노드가 root 노드이면 리프노드는 0개다.
            answer = 0;
        }

• DFS로 트리를 순회하며, 리프노드를 센다.

전체 코드

import java.util.*;

//노드를 표현할 클래스 선언
class Node{
    ArrayList<Node> child; //자식들을 가지고 있다.

    public Node() {
        this.child = new ArrayList<>();
    }
}

public class Main {
    static int answer = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] input = new int[n];
        int root =0;
        for (int i = 0; i < n; i++) {
            input[i] = scanner.nextInt();
            //입력 중 -1이면 해당 노드는 루트노드이다.
            if(input[i]==-1) root = i;
        }
        int deleteNode = scanner.nextInt();

        //트리 선언
        ArrayList<Node> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) tree.add(new Node());

        //노드간의 관계 연결
        for(int i=0; i<n; i++){
            if(input[i]!=-1) tree.get(input[i]).child.add(tree.get(i));
        }

        if(deleteNode!=root) { //삭제 노드가 root 노드가 아닐 경우
            // 부모노드에서 삭제 노드를 제거한다.
            tree.get(input[deleteNode]).child.remove(tree.get(deleteNode));
            DFS(tree.get(root)); //DFS로 리프노드 개수를 센다.
        }else{ // 삭제 노드가 root 노드이면 리프노드는 0개다.
            answer = 0;
        }

        System.out.println(answer);

    }
    //자식 노드를 탐색하며, 리프 노드를 센다.
    static void DFS(Node node){
        //자식노드가 없다면, 리프노드이다.
        if(node.child.size()==0){
            answer++;
            return;
        }else {
            //리프노드가 아니라면 자식노드 탐색
            ArrayList<Node> childNodes = node.child;
            for (Node childNode : childNodes) {
                DFS(childNode);
            }
        }
    }
}