프로그래머스 양과 늑대 (JAVA)

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

프로그래머스

 

저는 dfs를 이용해 문제를 해결하였습니다.

다른 dfs랑은 조금 다르게 다음에 갈 수 있는 경로를 파라미터로 주었습니다. 

갔던 곳을 또 갈 수 있지만, 그때 양과 늑대가 카운터되지 않기 때문에 위와 같이 구현하였습니다.

 

import java.util.*;

class Solution {
    private static final int WOLF = 1;
    private static final int SHEEP = 0;
    public int solution(int[] info, int[][] edges) {
        int size = info.length;
        List<Integer>[] map = new List[size];
        for(int i = 0 ; i < size ; i++){
            map[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int start = edge[0];
            int end = edge[1];
            map[start].add(end);
        }
        int answer = cal(0,0,0,info,map,new ArrayList<>());
        return answer;
    }
    private static int cal(int now,int sheep,int wolf,int[] info, List<Integer>[] map, List<Integer> list){
        if(info[now] == SHEEP){
            sheep++;
        }else{
            wolf++;
        }
        if(wolf >= sheep){
            return 0;
        }
        int result = sheep;
        List<Integer> temp = new ArrayList<>();
        for(int next : map[now]){
            temp.add(next);
        }
        for(int next : list){
            if(next == now){
                continue;
            }
            temp.add(next);
        }
        for(int next : temp){
            result = Math.max(result,cal(next,sheep,wolf,info,map,temp));
        }
        return result;
    }
}