[백준] 알고리즘 분류(트리,JAVA)1068번, 트리

문제 링크

1068번: 트리

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. -1로 주어지는 노드가 루트 노드가 됩니다.

2. 트리에서 지워야 할 노드를 지운 후 리프 노드의 개수를 결과로 출력합니다.

3. 리프 노드란 자식 노드가 존재하지 않는 단말 노드입니다.

 

알고리즘 진행 순서.

 

1. 입력된 트리의 정보를 저장합니다.

 

2. 입력된 정보를 가지고 트리의 형태로 만든 후 DFS탐색으로 리프 노드를 찾습니다.

※제거된 노드는 탐색하지 않습니다.

 

3. 리프노드이 개수를 결과로 출력합니다.

 

트리 만들기.

 

ArrayList<ArrayList<>>을 이용해서 각 노드가 어떤 자식 노드를 가지고 있는지 저장하였습니다.

 

예를 들어 아래와 같은 트리일 때

ArrayList.get(0) = { 1, 2 }가 저장되도록 하였습니다.

 

 

예제입력 1.

 

1. 입력된 트리의 정보를 저장합니다.

 

N = 5

 

노드의 부모 노드 정보 : -1, 0, 0, 1, 1

 

지울 노드 : 2

 

 

2. 입력된 정보를 가지고 트리의 형태로 만든 후 DFS탐색으로 리프 노드를 찾습니다.

※제거된 노드(2)는 탐색하지 않습니다.

 

루트 노드 : 0에서 탐색 시작!

다음 노드 : 1에서 탐색 시작!

다음 노드 : 3에서 탐색 시작!

 

자식 노드가 발견되지 않았기 때문에 리프 노드 확정!

다음 노드 : 4에서 탐색 시작!

자식 노드가 발견되지 않았기 때문에 리프 노드 확정!

 

3. 리프노드이 개수를 결과로 출력합니다.

 

찾은 리프 노드 : 3, 4

 

2을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리의 정보를 띄어쓰기 기준으로 나누었습니다.
• 입력값을 토대로 트리를 형성한 뒤 삭제할 노드를 저장하였습니다.
• 삭제할 노드가 루트노드이면 리프 노드는 0개, 루트 노드가 아니면 search함수를 실행하였습니다.
• 리프 노드의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 트리를 DFS탐색을 진행하여 리프 노드를 찾습니다.
• search함수는 삭제할 자식 노드에는 접근하지 않도록 하였습니다.

 

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

public class Main {
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();	//트리 정보 저장 리스트
    static int answer = 0;		//리프 노드 개수 변수
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());	//노드의 개수 입력값 저장
        int root = 0;		//루트 노드 기본값 설정
        //트리에 대한 ArrayList 초기화
        for(int i=0;i<=N;i++)
            tree.add(new ArrayList<>());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //트리의 정보 저장
        for(int i=0;i<N;i++){
            int node = Integer.parseInt(st.nextToken());
            //루트 노드의 값 저장
            if(node == -1){
                root = i;
                continue;
            }
            tree.get(node).add(i);	//일반 노드의 값들 저장
        }
        //삭제할 노드 입력값 저장
        int remove = Integer.parseInt(br.readLine());
        //삭제할 노드와 루트 노드가 같으면 트리 전체가 삭제!
        if(remove == root)
            answer = 0;		//트리가 없으면 리프 노드도 0개
        else		//루트 노드가 아닌 다른 노드 삭제시 DFS 탐색!
            search(remove, root);
        bw.write(answer + "");		//리프 노드 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //루트 노드부터 DFS탐색으로 리프 노드를 찾는 재귀 함수
    static void search(int remove, int node){
        //현재 노드의 삭제할 노드 포함시 삭제!
        if(tree.get(node).contains(remove))
            tree.get(node).remove(Integer.valueOf(remove));
 
        //현재 노드가 리프 노드일 때
        if(tree.get(node).isEmpty()){
            answer++;
            return;
        }
        //자식 노드가 존재할 때 DFS 탐색!
        for(int next : tree.get(node)){
            search(remove, next);
        }
    }
}