Programmers - 양과 늑대 with JAVA

 

 

 

 

로직  - DFS

 

 

 

위와 같은 상황이 있다고 가정하자.

dfs의 시작은 노드번호 0부터 시작한다.

1 : 0번 방문) next = {1, 8}, 양 = 1, 늑대 = 0

2 : 0-1번 방문) next = {8, 2, 4}, 양 = 2, 늑대 = 0 

3 : 0-8번 방문) next = {1, 7, 9}, 양 = 1, 늑대 = 1      -> 하지만 양과 늑대 수가 같아지므로 제외됨.

4 : 0-1-8번 방문) next = {2, 4, 7, 9} 양 = 2, 늑대 = 1

...

 

즉, 방문마다 다음 방문할 노드로 해당 노드의 자식 노드들은 추가하되, 형제 노드도 추가해주면서 DFS를 돌리는 방식으로 이 문제를 해결할 수 있다.

 

 

 

 

 

 

코드

import java.util.*;
class Solution {
    public static int answer = 0;
    public static List<List<Integer>> childs = new ArrayList<>();
    public static int[] new_info;
	public static int solution(int[] info, int[][] edges) {
        new_info = info;
        for(int i=0; i<info.length; i++){
            childs.add(new ArrayList<>());
        }
        for(int[] edge : edges){
            childs.get(edge[0]).add(edge[1]);
        }
        System.out.println(childs);
        List<Integer> next = new ArrayList<>();
        next.add(0);
        dfs(0, 0, 0, next);
		return answer;
	}
    public static void dfs(int num, int sheep, int wolf, List<Integer> next){
        sheep += (new_info[num] == 0) ? 1 : 0;
        wolf += (new_info[num] == 1) ? 1 : 0;
        if(sheep <= wolf){
            return;
        }
        answer = Math.max(sheep, answer);
        List<Integer> new_next = new ArrayList<>();
        new_next.addAll(next);
        new_next.remove(Integer.valueOf(num));
        for(int child : childs.get(num)){
            new_next.add(child);
        }
        for(int new_num : new_next){
            dfs(new_num, sheep, wolf, new_next);
        }
    }
}