문제 바로가기

정답 코드

import java.util.*;
import java.io.*;

class Solution {
    static Set<Integer> visited;
    static List<Integer>[] adj;
    static int maxSheep;
    static int[] info;
    
    public int solution(int[] info, int[][] edges) {
        maxSheep=0;
        int n=info.length;
        visited=new HashSet<>();
        adj=new ArrayList[n];
        for(int i=0;i<n;i++){
            adj[i]=new ArrayList<>();
        }
        this.info=info;
        
        for(int[] edge:edges){
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        visited.add(0);
        dfs(0,1,0,visited);
        return maxSheep;
    }
    
    static void dfs(int idx, int sheep, int wolf, Set<Integer> visited){
        if(wolf>=sheep){
            return;
        }
        
        maxSheep=Math.max(sheep,maxSheep);
        
        for(int i:visited){
            for(int j:adj[i]){
                if(!visited.contains(j)){
                    Set<Integer> visited2=new HashSet<>(visited);
                    visited2.add(j);
                    
                    if(info[j]==0){
                        dfs(idx+1, sheep+1, wolf, visited2);    
                    }else{
                        dfs(idx+1, sheep, wolf+1, visited2);
                    }
                }
            }
        }
    }
}

solution 파라미터 전역변수로 사용하는 법

가끔씩 파라미터를 전역으로 사용해야할때가 있는데 그럴때 어떻게 해야하는지 몰랐다.
이렇게 this.를 쓰면된다.

this.info=info;

왜 set을 복사해서 써야하지?

Set<Integer> visited2=new HashSet<>(visited);
visited2.add(j);

dfs 분기가 같은 set을 쓰면 안되기 때문에.
독립적으로 방문상태를 봐줘야하기 때문이라고 한다.