[SWEA] 2112. 보호 필름

부분집합의 개념이 사용된 문제이다.

이 문제는 부분집합의 개념으로 구현할수 있는 문제이다. 즉 하나의 행에 대해 1. 변화를 안준다. 2. 0으로 다바꾼다. 3. 1로 다바꾼다. 를 가질수 있고 전체 경우의 수를 구해보면 3^(행의수) 를 가지게 된다. 전체 경우의 수를 구함에 있어 재귀를 사용하여 구해주었다. 재귀를 함에 있어 최적화를 시키려면 가지치기가 상당히 중요하다. 이 문제에선 변화를 주는 횟수를 세어주는 count 변수가 작을때를 구하게 되는 문제인데, 가지치기를 위해 현재 가지고 있는 count보다 큰경우는 바로 return을 해주는 방식으로 가지를 쳐주었다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution_2112_보호필름 {
    static int D,W,K;
    static int[][] map;
    static int answer;
    
    static int[] pick;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T=Integer.parseInt(br.readLine());
        for(int tc=1;tc<=T;tc++) {
            st=new StringTokenizer(br.readLine());
            D=Integer.parseInt(st.nextToken());
            W=Integer.parseInt(st.nextToken());
            K=Integer.parseInt(st.nextToken());
            map=new int[D][W];
            for(int i=0;i<D;i++) {
                st=new StringTokenizer(br.readLine());
                for(int j=0;j<W;j++) {
                    map[i][j]=Integer.parseInt(st.nextToken());
                }
            }
            
            pick=new int[D];
            answer=Integer.MAX_VALUE;
            subSet(0,0);
            System.out.println("#"+tc+" "+answer);
        }
    
    }
    
    static void subSet(int depth, int count) {
        if(count >= answer)        //가지치기
            return;
        
        if(depth==D) {
            if(check()==true) {
                answer=Math.min(answer, count);
            }
            return;
        }
        
        
        
        
        pick[depth]=0;            //그대로
        subSet(depth+1, count);
        
        pick[depth]=1;            //0으로
        subSet(depth+1, count+1);
        
        pick[depth]=2;            //1로
        subSet(depth+1, count+1);
        
    }
    
    static boolean check() {
        int[][] test=new int[D][W];
        for(int i=0;i<D;i++) {
            if(pick[i]==0) {
                for(int j=0;j<W;j++) {
                    test[i][j]=map[i][j];
                }
            }else {
                for(int j=0;j<W;j++) {
                    test[i][j]=pick[i]-1;
                }
            }
        }
        
        
        for(int col=0;col<W;col++) {
            boolean ok=false;
            for(int start=0;start<=D-K;start++) {
                int count=0;
                int flag=test[start][col];
                for(int next=start;next<start+K;next++) {
                    if(test[next][col]!=flag) {
                        break;
                    }else {
                        count+=1;
                    }
                }
                if(count==K) {
                    ok=true;
                    break;
                }
            }
            if(ok==false) {
                return false;
            }
        }
        
        return true;
    }
}