swe 2112 보호 필름

- 중복 가능한 순열 - 거기에다가 cnt 의 조건 하나 더 추가 - dfs 확인 할 때 가지치기의 중요성 - 안되면 바로 빠져나오도록 설계해야 합니다. (이거 걸릴 줄 이야...) 아이디어, 맵을 변경하지 않고, 확인하는 방법이 존재한다는 것 꼼꼼한것이 중요. 일단 dfs+시뮬이면 dfs 가 명확하게 나오는지 확인할 필요가 있음.

/*

*/
 
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
#define SIZED  13// 13 
#define SIZEW  21// 21
int dataArr[SIZED];
int map[SIZED][SIZEW];
int D, W, K;
int minVal = 2123456789;
int isFine;
int curC;
int conti_cnt;
int one_down;
 
void problemIn() {
    cin >> D >> W >> K;
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map[i][j];
        }
    }
}
 
void init() {
    minVal = 2123456789;
    isFine = 0;
    conti_cnt = 0;
    one_down = 0;
    curC = 0;
    memset(dataArr, 0, sizeof(dataArr));
    memset(map, 0, sizeof(map));
}
 
/* 현재 dataArr에 투약할 약품의 색이 들어 있습니다.


*/
void check(int cnt2) {
 
    for (int j = 0; j < W; j++) {
        curC = (dataArr[0] == 2) ? map[0][j] : dataArr[0];
        conti_cnt = 1;
        for (int i = 1; i < D; i++) {
            //현재가 다음 데이터와 같다면,
            one_down = dataArr[i] == 2 ? map[i][j] : dataArr[i];
            if (curC == one_down) {
                conti_cnt++;
                if (conti_cnt >= K) {
                    isFine = 1;
                    break;
                }
            }
            else {
                curC = one_down;
                conti_cnt = 1;
                isFine = 0;
            }
        }
        if (isFine == 0) { // 한열에 대해서 검사를 했는데, 연속된 숫자가 K개 이하면,
            return; // 이번은 안됨, 다른 투약이 필요함.
        }
    }
 
    // 모든 열을 다 돌았는데, okay 이면,
    if (isFine) {
        minVal = min(minVal, cnt2);
        return;
    }
}
 
void dfs(int depth, int cnt) {
 
    if (depth == D) {
        check(cnt);
        return;
    }
 
    if (cnt < K) {
        for (int i = 2; i >= 0; i--) {
            dataArr[depth] = i;
            dfs(depth + 1, (i == 2) ? cnt : cnt + 1);
        }
    }
}
 
void solve() {
    if (K == 1) {
        minVal = 0;
        return;
    }
    else {
        dfs(0, 0);
    }
}
 
int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        problemIn();
        solve();
        cout << "#" << tc << " " << minVal << endl;
        init();
    }
    return 0;
}