[2022 KAKAO BLIND RECRUITMENT] 양과 늑대

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=java

이 문제는 백트래킹을 이용하여 문제를 풀 수 있습니다. 주어진 제한 조건이 17로 작은 편이기 때문에 백트래킹을 이용해도 시간 초과가 발생하지 않게 됩니다. 이 때 check 배열을 3차원으로 [현재 노드][양 개수][늑대 개수] 로 설정하여 늑대 개수가 양 수보다 많을 때 리턴하는 방식으로 종료 시점을 설정했습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static ArrayList<Integer>[] graph = new ArrayList[17];
    static boolean[][][] check = new boolean[17][18][18];
    static int max = 0;
    
    static void backtracking(int[] info, int node, int sheep, int wolves){
        if(info[node]==0) sheep++;
        else if(info[node]==1) wolves++;
        
        if(sheep <= wolves) return;
        
        if(max < sheep) max = sheep;
        
        ArrayList<Integer> curr = graph[node];
        
        for(int i=0;i<curr.size();i++){
            int child = graph[node].get(i);
            int tmp = info[node];
            
            if(!check[node][sheep][wolves]){
                check[node][sheep][wolves] = true;
                info[node] = -1;
                backtracking(info,child,sheep,wolves);
                check[node][sheep][wolves] = false;
                info[node] = tmp;
            }
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        for(int i=0;i<info.length;i++) graph[i] = new ArrayList<>();
        for(int i=0;i<edges.length;i++){
            int p = edges[i][0];
            int c = edges[i][1];
            
            graph[p].add(c);
            graph[c].add(p);
        }
        
        backtracking(info,0,0,0);
        return max;
    }
}