양과 늑대

문제 설명

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

제한사항

2 ≤ info의 길이 ≤ 17
info의 원소는 0 또는 1 입니다.
info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
0은 양, 1은 늑대를 의미합니다.
info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
edges의 세로(행) 길이 = info의 길이 - 1
edges의 가로(열) 길이 = 2
edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
0번 노드는 항상 루트 노드입니다.

변형 DFS문제이다.
0번은 무조건 양이기 때문에 0번부터 시작하고 이를 그래프로 연결하여 리스트를 확인하여 늑대가 양보다 많아지면 종료하고 아니라면 계속 하면된다.

문제는 완전하게 양만 존재한다고 했을때 이트리를 완전탐색한다면 2^17만큼의 탐색이 필요하므로 시간초과가 생긴다. 따라서 비트마스크를 이용한 방식이나 set을 이용한 방식같은 이미 확인한 중복트리를 제외하는 코드가 필요하다.

코드

import java.util.*;
class Solution {
    HashSet<boolean[]> set;
    ArrayList<Integer>[] list;
    int sheep=0;
    
    public int solution(int[] info, int[][] edges) {
        list = new ArrayList[info.length];
        set = new HashSet<>();
        for(int[] e :edges){
            if(list[e[0]]==null) list[e[0]] = new ArrayList<Integer>();           
            list[e[0]].add(e[1]);                           
        }
        ArrayList<Integer> tmp = new ArrayList<>();
        tmp.add(0);
        dfs(0,0,0,tmp,info,new boolean[info.length]);
     
      
        
        return sheep;
    }
    void dfs(int wolf,int sheep,int idx,List<Integer> nextMove,int[] info,boolean[] visit){
         visit[idx]=true;
   
         if(visitList(visit)){           
             return;
         }else{
            set.add(visit);
         }
    
            
        if(info[idx]==0) sheep++;
        else wolf++;
        if(wolf>=sheep) return;
        this.sheep=Math.max(sheep,this.sheep);
        List<Integer> tmp = new ArrayList<>(nextMove);
        tmp.remove(Integer.valueOf(idx));
		if (list[idx] != null) {
			for (int l : list[idx]) {
				tmp.add(l);
			}
		}

        for (int t : tmp) {
            boolean[] b= visit.clone();
			dfs(wolf,sheep,t,tmp,info,b);
		}
    }
   boolean visitList(boolean[] visit){            
       for (boolean[] s : set) {
           if(Arrays.equals(s, visit)){
               return true;
           }
       }          
       return false;
   }
}

set.contains가 배열끼리의 비교에서 문제가 생기는것을 확인했다.
아마 hashcode의 문제인것같은데 제대로 확인해봐야겠다.