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

 

완전 탐색인데 생각보다 까다로웠던 문제.
어떻게 풀어야하는지는 알았는데 구현이 어려웠다..!

import java.util.*;

class Solution {
    private int[] info;
    private Map<Integer, Set<Integer>> tree;
    
    public int solution(int[] info, int[][] edges) {
        this.info = info;
        this.tree = new HashMap<>();
        
        for (int i = 0; i < info.length; i++) {
            tree.put(i, new HashSet<>());
        }
        
        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
        }
        
        Set<Integer> nextPossible = new HashSet<>(tree.get(0));
        return dfs(0, 0, 0, nextPossible);
    }
    
    private int dfs(int sheep, int wolf, int current, Set<Integer> possible) {
        if (info[current] == 0) {
            sheep++;
        } else {
            wolf++;
        }
        
        if (wolf >= sheep) {
            return 0;
        }
        
        int maxSheep = sheep;
        
        for (int next : possible) {
            Set<Integer> nextPossible = new HashSet<>(possible);
            nextPossible.remove(next);
            nextPossible.addAll(tree.get(next));
            maxSheep = Math.max(maxSheep, dfs(sheep, wolf, next, nextPossible));
        }
        
        return maxSheep;
    }
}