[SWEA]#2112 보호 필름

문제

2112. [모의 SW 역량테스트] 보호 필름

풀이

이 문제는 DFS 알고리즘을 이용해서 경우의 수를 모두 구해서 풀 수 있었다.

import java.io.InputStreamReader;
import java.io.BufferedReader;

class Solution {
    static int D;
    static int W;
    static int K;
    static int min;
    static int[][] map;
    static int[][] current_map;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int test_case=1; test_case<=T; test_case++) {
            String[] input = br.readLine().split(" ");
            D = Integer.parseInt(input[0]);
            W = Integer.parseInt(input[1]);
            K = Integer.parseInt(input[2]);
            map = new int[D][W];
            current_map = new int[D][W];
            min = Integer.MAX_VALUE;

            for(int i=0; i<D; i++) {
                input = br.readLine().split(" ");
                for(int j=0; j<W; j++) {
                    map[i][j] = Integer.parseInt(input[j]);
                    current_map[i][j] = map[i][j];
                }
            }

            if(check(map)) {
                System.out.println("#"+test_case+" 0");
                continue;
            }

            dfs(0, 0);
            System.out.println("#"+test_case+" "+min);
        }
    }

    public static void dfs(int idx, int cnt) {
        if(cnt>=min) return;

        if(idx==D) {
            if(check(current_map))
                min = cnt;
            return;
        }
        dfs(idx+1, cnt);

        for(int j=0; j<W; j++) {
            current_map[idx][j] = 0;
        }
        dfs(idx+1, cnt+1);

        for(int j=0; j<W; j++) {
            current_map[idx][j] = 1;
        }
        dfs( idx+1, cnt+1);

        for(int j=0; j<W; j++) {
            current_map[idx][j] = map[idx][j];
        }
    }

    public static boolean check(int[][] map) {
        boolean flag = true;
        int n;

        loop:for(int j=0; j<W; j++) {
            n = 1;
            for(int i=1; i<D; i++) {
                if(n==K) continue loop;
                if(map[i][j]==map[i-1][j]) n++;
                else n=1;
            }
            if(n<K) flag=false;
        }
        return flag;
    }
}