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

풀이

1. 먼저 배열 탐색을 통해 합격 기준을 판별하는 함수인 checkPass() 함수를 구현한다.
2. 해당 함수는 각 행들을 탐색하며 연속으로 K개의 숫자가 있는지 판별하며, 특정 행에서 이를 만족시키지 못하면 false를 반환하고 모두 통과하게 되면 true를 반환한다.
3. 이후 각 테스트케이스마다 checkPass()함수를 실행 후, 한번에 통과하지 못하면 백트래킹 함수를 실행한다.
4. 백트래킹 함수의 파라미터는 행의 레벨, 바뀐 행의 수로 세팅하였다. 또한 백트래킹 함수의 가지치기 조건으로는 변환 횟수가 현재 최소 변환 수보다 크게 되면 반환하도록 하였다.
5. 바텀-업 방식을 사용하여, 먼저 가장 마지막 행까지 재귀를 돌린 후, 돌아오는 과정에서 각 행들을 A(0), B(로) 각각 채우며, 바뀐 횟수를 증가시켜 마지막 행에 이르면 checkPass() 함수를 통해 최소 변경 횟수를 구한다.
6. 함수 내에서 각 행들을 바꾸고 돌아오는 과정에서 기존 값들을 임시 저장시킨 값으로 다시 복구해주었다.

#include <iostream>
#include <algorithm>
using namespace std;

int T, D, W, K;
int arr[14][21];
int ans;

bool checkPass() {
    for (int j = 0; j < W; j++) {
        int maxCnt = 1;
        int cnt = 1;
        for (int i = 1; i < D; i++) {
            if (arr[i][j] == arr[i - 1][j]) {
                cnt++;
                maxCnt = max(maxCnt, cnt);
            } else {
                cnt = 1;
            }
        }
        if (maxCnt < K) return false;
    }
    return true;
}

void BT(int lev, int changed) {
    if (changed >= ans) return;

    if (lev == D) {
        if (checkPass())
            ans = min(ans, changed);
        return;
    }

    BT(lev + 1, changed);
    int tmp[21];
    for (int j = 0; j < W; j++)
        tmp[j] = arr[lev][j];

    for (int j = 0; j < W; j++)
        arr[lev][j] = 0;
    BT(lev + 1, changed + 1);

    for (int j = 0; j < W; j++)
        arr[lev][j] = 1;
    BT(lev + 1, changed + 1);

    for (int j = 0; j < W; j++)
        arr[lev][j] = tmp[j];
}

int main() {
    cin >> T;
    for (int k = 0; k < T; k++) {
        ans = 30;
        cin >> D >> W >> K;
        for (int i = 0; i < D; i++)
            for (int j = 0; j < W; j++)
                cin >> arr[i][j];

        if (checkPass()) {
            cout << "#" << k + 1 << " " << 0 << "\n";
            continue;
        }

        BT(0, 0);
        cout << "#" << k + 1 << " " << ans << "\n";
    }
    return 0;
}