문제 - 양과 늑대

문제 설명

루트노드부터 출발하면서 최대한 양을 모은다. 양과 늑대의 수가 같아지거나 늑대의 수 가 많아질 경우에는 양이 잡아먹힌다. 그래서 양의 수가 늑대보다 더 많아야된다.
그래서 위의 그림은 0 -> 1-> 8-> 7-> 9-> 4 -> 6-> 5로 방문을 하게 되면 양은 5마리 늑대는 3마리로 최대한 많은 양을 모을 수 있다.

문제 접근

처음에는 어떻게 접근을 해야될지 몰랐었다. 모든 노드를 왔다갔다하면서 완전탐색으로 할려고했는데 방문처리는 어떻게 해야될지도 잘모르겠어서 한참 고민을 했다.
그래서 방문을 하면서 양의 수가 더 많은 경우 즉 다음 노드로 이동할 수 있을 때 현재의 노드를 빼는 식으로 이동했다.

1. 각 노드별로 연결을 한다. 부모노드 -> 자식노드로만 연결하면 된다.
2. 루트노드부터 시작하기때문에 다음 경로에 0을 추가
3. 다음 경로 0의 노드의 자식노드를 다음 경로에 추가한다. 그리고 현재 노드를 삭제한다.
4. 다음 경로의 노드부터 늑대보다 양의 수가 더 많은 경우에만 다음 노드로 이동하면서 최대 모을 수 있는 양을 체크한다.

import java.util.*;


class Solution {
    int answer = 0;
    ArrayList<Integer> []graphs;
    public int solution(int[] info, int[][] edges) {
        
        //노드별 연결
        graphs = new ArrayList[info.length];
        
        for(int []edge : edges)
        {
            if(graphs[edge[0]] == null)
            {
                graphs[edge[0]] = new ArrayList<>();
            }
            
            graphs[edge[0]].add(edge[1]);
        }
        ArrayList<Integer> next = new ArrayList<>();
        next.add(0);//루트노드부터 시작
        
        dfs(0,0,0,info,next);
        
        return answer;
    }
    
    public void dfs(int idx, int sheep,int wolf, int []animal,ArrayList<Integer> list)
    {
        //양인 경우
        if(animal[idx] == 0)
        {
            sheep++;
        }else{
            wolf++;
        }
        
        //늑대가 양보다 같거나 큰 경우 제외 
        if(sheep <= wolf) return;
        answer = Math.max(sheep,answer);
        
        ArrayList<Integer> next = new ArrayList<>();
        next.addAll(list);
        //현재 있는 노드 삭제
        next.remove(next.indexOf(idx));
        
        if(graphs[idx] != null)//자식노드가 있는 경우
        {
            for(int node : graphs[idx])
            {
                next.add(node);
            }
        }
        
        
        for(int n: next)
        {
            dfs(n,sheep,wolf,animal,next);
        }
    }
}