[백준] 1068번 트리 JAVA (자바) 풀이

문제 1068번 (dfs)

 

 :  리프 노드 = 자식의 개수가 0인 노드

    노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거

    남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성

 

 예) 리프 노드의 개수는 3개

 이때, 1번을 지우면, 다음과 같이 변한다. 회색으로 색칠된 노드가 트리에서 제거

 이제 리프 노드의 개수는 1개

 

 

 [입력]

 :  첫째 줄에 트리의 노드의 개수 N (N은 50보다 작거나 같은 자연수)

 :  둘째 줄에는 0번 ~ N-1번 노드까지 각 노드의 부모가 주어진다
    (만약 부모가 없다면 -1)

 :  셋째 줄에는 지울 노드의 번호

 

 

 [출력]

 :  첫째 줄에 주어진 노드를 지웠을 때, 남은 리프 노드의 개수를 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs 

 

 1. 부모는 하나지만 자식은 여러개일 수 있다

•  부모를 인덱스로, 자식은 arrayList 값에 다중 추가할 것

 

 2. -1인 인덱스 root란 객체에 따로 저장

• -1 일 경우 가장 상단의 뿌리이므로 이지점부터 시작한다
• 가장 상단부터 시작하는 이유는 순차적으로 내려오면서 계산하는게 제일 편하다
• remove 지점을 만나는 순간 더이상 아래로 내려가지 않아도 될 뿐만아니라
  자식수를 계산하며 내려오기 때문에 리프노드인 지 구분이 가능하다

 

 3. remove가 아니면서 방문 전이라면

• 해당 지점을 시작지점으로 두어 dfs 다시반복
• 방문했거나 더이상 아래로 내려갈 수 없다면 child = 0이며
  이는 리프노드임을 뜻하기 때문에 count++ 한다              

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,remove;
    static int count =0;
    static boolean visit[]; 
    static List<Integer> tree[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        visit = new boolean[N];
        
        tree = new ArrayList[N];
        for(int i=0;i<N;i++){
            tree[i] = new ArrayList<>();
        } 
        
        int root = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            int p = Integer.parseInt(st.nextToken());
            if(p!=-1){
                tree[p].add(i);
            }
            else{
                root = i;
            }
        }
        
        remove = Integer.parseInt(br.readLine());
        
        if(remove==root){
            System.out.println(0);
        }else{
            dfs(root);
            System.out.println(count);
        }
    }
    
    static void dfs(int n){
        visit[n] = true;
        int child = 0;
        for(int i:tree[n]){
            if(i!=remove&&!visit[i]){
                child++;
                dfs(i);
            }
        }
        if(child==0){
            count++;
        }
    }
}

 

 [해설]
     

 :  static int N,remove;  
    static int count =0;
    static boolean visit[]; 
    static List<Integer> tree[];

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());  첫번째 입력
    visit = new boolean[N];  방문기록 초기화
        
 :  tree = new ArrayList[N];  부모-자식 연결 트리 초기화
    for(int i=0;i<N;i++){
            tree[i] = new ArrayList<>();
    } 
        
 :  int root = 0;  가장 상단의 루트를 저장할 객체
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i=0;i<N;i++){  두번째줄 입력 (연결된 부모)
            int p = Integer.parseInt(st.nextToken());
            if(p!=-1){  상단의 노드가 아니라면 현재 인덱스가 입력받은 수의 자식이 된다
                tree[p].add(i);  입력받은 수를 트리의 인덱스로 지정
            }
            else{  -1 이면 최상단의 노드
                root = i; 
            }
    }
        
 :  remove = Integer.parseInt(br.readLine());  세번째줄 입력 제거할 노드
        
    if(remove==root){  제거할 대상이 최상단 노드라면 0출력
            System.out.println(0);
    }

    else{
            dfs(root);  dfs 실행
            System.out.println(count);  count 출력
    }
    
    
 :  static void dfs(int n){  최상단 노드부터 탐색 시작
        visit[n] = true;  방문처리
        int child = 0;  연결된 자식수 계산
        for(int i:tree[n]){ 
            if(i!=remove&&!visit[i]){  제거대상이 아니고 방문전이라면 더욱 깊이 전진
                child++;  자식수 체크
                dfs(i);  다음 깊이를 기준으로 dfs 실행
            }
        }
        if(child==0){  자식이 없다는건 더이상 내려갈 수 없다
            count++;  리프노드임을 체크
        }
    }


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *