[SWEA] 2112. 보호필름

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

import java.util.StringTokenizer;

public class Solution_2112_보호필름 {
    static int[][] film, temp;
    static int D, W, K, res;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(in.readLine());

        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(in.readLine());

            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            film = new int[D][W];
            temp = new int[D][W];

            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(in.readLine());
                for (int j = 0; j < W; j++) {
                    film[i][j] = temp[i][j] = Integer.parseInt(st.nextToken());
                }
            } // 입력

            res = Integer.MAX_VALUE;

            if (isPass()) {
                res = 0;
            } else {
                injection(0, 0);
            }
            sb.append("#" + tc + " " + res+"\n");

        }
        out.write(sb.toString());
        out.flush();
        out.close();
    }

    private static void injection(int cnt, int layer) {
        if (cnt >= res) // 가지치기 약품주입횟수가 최소약품주입횟수보다 커지면 더이상 볼 필요가 없어짐
            return;

        if (layer == D) { // 끝까지 다 봤으면 
            if (isPass()) {
                res = Math.min(res, cnt);
            }
            return;
        }

        // 주입하지 않음
        injection(cnt, layer + 1);

        // A 주입
        for (int c = 0; c < W; c++) {
            temp[layer][c] = 0;
        }
        injection(cnt + 1, layer + 1);

        // B 주입
        for (int c = 0; c < W; c++) {
            temp[layer][c] = 1;
        }
        injection(cnt + 1, layer + 1);

        // 되돌리기
        for (int c = 0; c < W; c++) {
            temp[layer][c] = film[layer][c];
        }
    }

    private static boolean isPass() {
        for (int c = 0; c < W; c++) {
            int cnt = 1;
            int type = temp[0][c]; // 각 줄의 첫번째 요소
            boolean flag = false; // 각 줄을 검사할 falg

            for (int r = 1; r < D; r++) { // 각 줄의 각 요소를 검사함 (K개 연속인지 아닌지)

                if (type == temp[r][c]) { // 요소가 줄의 첫번째 요소와 같을 때 cnt 증가
                    cnt++;
                } else { // 다를 때 type 바꿈cnt 1로 초기화
                    type = temp[r][c];
                    cnt = 1;
                }
                if (cnt == K) { // 한 줄 끝나기 전에 K개 연속이면
                    flag = true;
                    break; // 그 줄은 더이상 검사 안해도 됨. 다음 줄로 넘어감
                }
            } // 한 줄 끝남
            if (!flag) // 한줄 끝났는데도 K개 연속이 안되면 false return 하고 끝
                return false;
        }
        return true; // 모든 줄을 검사했는데도 flag가 false가 된 적 없으면 모든 줄이 K개 연속인 부분이 있다는 뜻이므로 true 출력
    }
}

익혀야 할 내용

• if(isPass())에서 전역으로 선언해서 isPass()로 메서드를 따로 빼서 검사
• 연속된 수가 있는지 검사할 때 나는 슬라이딩 윈도우를 쓰려고 해서 풀이가 복잡해지는 느낌이 있었는데 isPass 메서드처럼 개수를 세는 방식으로 검사하는 방법이 간단하고 더 좋은듯
• 이 문제에서 나오는 백트래킹 모양을 외워야겠다. 주목해야 될 부분은 가지치는 부분과 주입하지 않음/A주입/B주입/되돌리기
• 인자를 cnt와 layer 2개로 둬서 백트래킹 하는 법을 익혀야 겠다.