[JAVA] 프로그래머스 LEVEL3 양과 늑대

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 양과 늑대

 

난이도: LEVEL3

알고리즘 유형: 이진트리 / 완전탐색 

 

문제의 핵심 

해당 문제는 단순한 DFS / BFS 통해서 이진 트리를 탐색하면 정답을 못 찾는 문제이다. 

그 이유를 설명하겠다.

 

프로그래머스에서 제공한 첫 번째 입출력 (정답은 5) 

 

정답 5인 이진 트리 탐색 경로 

양:5 늑대:3 정답은 5 

 

단순한 BFS/DFS 통한 탐색은 절대 이런 경로를 찾지 못한다.

 

단순한 DFS(왼쪽이 먼저)로 나오는 경로

 

0 → 1                                    양:2  늑대:0

0 → 1 →  2                           양:2  늑대:1

0 → 1 →  4                           양:2  늑대:1

0 → 1 →  4 →  3                  양:2  늑대:2 (양 <= 늑대 return)

0 → 1 →  4 →  6                  양:2  늑대:2 (양 <= 늑대 return)

 

0 → 8                                   양:1 늑대:1 (양 <= 늑대 return)

 

BFS 예시 

 

BFS 오른쪽 먼저 이동하는 탐색 예시이다.

BFS의 8번 정점에서의 자식 정점은 7번 정점 9번 정점이 있는데

BFS/DFS 모두 해당 정점에서 7번 정점 9번 정점을 모두 포함하는 탐색은 불가능하다.

 

그래서 문제를 풀려면 이진 트리를 완전탐색 해야한다.

 

정답 코드 

import java.util.*;
class Solution {
    static int [] infos;
    static int [][] tree = new int [21][2];
    static int answer = 0;
    public int solution(int[] info, int[][] edges) {
        infos = info;
        for(int i = 0; i <= 20; i++){
            Arrays.fill(tree[i], -1);
        }
        for(int i = 0; i < edges.length; i++){
            int parent = edges[i][0];
            int child  = edges[i][1];
            if(tree[parent][0] == -1) tree[parent][0] = child;
            else tree[parent][1] = child;
        }  
        HashSet<Integer> list = new HashSet<>();
        list.add(0); // 루트 추가 
        search(1, 0, list);
        
        return answer;
    }
    public static void search(int sc, int wc, Set<Integer> list){
        if(sc <= wc) return;
        answer = Math.max(answer, sc); // 최댓값 갱신 
        
        for(int cur : list){
            if(tree[cur][0] != -1 && !list.contains(tree[cur][0])){ // left
                HashSet<Integer> set = new HashSet<>(list);
                set.add(tree[cur][0]);
                if(infos[tree[cur][0]] == 0){
                    search(sc + 1, wc, set);       
                }
                else search(sc, wc + 1, set);
            }
            
            if(tree[cur][1] != -1 && !list.contains(tree[cur][1])){ // right 
                HashSet<Integer> set = new HashSet<>(list);
                set.add(tree[cur][1]);
                if(infos[tree[cur][1]] == 0){
                    search(sc + 1, wc, set);       
                }
                else search(sc, wc + 1, set);
            }
        }
    }
}