[SW Expert Academy] 2112. 보호 필름

#include <iostream>
#include <cstring>
#include <algorithm>
#define p pair<int,int>
using namespace std;

int map[13][20];
int ans;
int row,col,k;

bool chk(){
    for(int c=0; c<col; c++){
        bool flag = true;
        /*
         row : 6
         k : 3 이라면
         체크해야하는 row의 범위는
         0 ~ 4이다.
         그러므로 row-k+1까지 해줘야한다.
         */
        for(int r=0; r<row-k+1; r++){
            flag = true;
            for(int i=1; i<k; i++){
                if(map[r][c] != map[r+i][c]){
                    flag = false;
                    break;
                }
            } // end of for i
            /*
             column을 기준으로
             연속으로 k만큼 성립한다면
             flag값은 true이다.
             그렇기 때문에
             현재 column은 조건을 충족시키기 때문에
             더이상 볼 필요가 없기에 탈출한다.
             */
            if(flag){
                break;
            }
        } // end of for r
        /*
         column에 대해
         모든 경우를 살폈는데
         가능한 경우가 없었다.
         즉 그 column에서는 조건을 충족시키지 못했다.
         그러면 다음 column을 볼 필요도 없이
         조건을 충족시키지 못하기 때문에
         false를 return한다.
         */
        if(! flag)
            return false;
    } // end of for c
    return true;
}

/*
 chk()보다 효율적으로 개선한 함수
 chk()같은 경우에는
 k=3 일 때
 각 row마다 k만큼 연속적인지 체크하고
 그 다음 row에 대해서도 반복한다.
 그런데 chk2()에서는 각 row는 1번만 체크한다.
 */
bool chk2(){
    for(int c=0; c<col; c++){
        bool flag = false;
        int cnt = 0;
        int color = -1;
        for(int r=0; r<row; r++) {
            int v = map[r][c];
            if (v == color) {
                cnt++;
            }
            else {
                cnt = 1;
                color = v;
            }
            if (cnt >= k) {
                flag = true;
                break;
            }
        } // end of for r
        if (!flag) {
            return false;
        }
    } // end of for c
    return true;
}


void dfs(int st_row, int cnt){ // st_row : 색을 칠할 Row Index
    /* st_row >= now 조건
     그냥 Pass할 경우 (= dfs(st_row+1,cnt) )
     st_row >= row 조건이 없다면
     Runtime Error가 발생한다.
     즉 무한 루프를 돌게 된다.
    */
    if( cnt == 0 || st_row >= row ){
        if(chk())
            ans = 1;
        return ;
    }
    
    int tmp_row[20];
    for(int j=0; j<col; j++) tmp_row[j] = map[st_row][j];
    dfs(st_row+1,cnt);
    
    for(int j=0; j<col; j++) map[st_row][j] = 0;
    dfs(st_row+1,cnt-1);
    
    for(int j=0; j<col; j++) map[st_row][j] = 1;
    dfs(st_row+1,cnt-1);
    
    for(int j=0; j<col; j++) map[st_row][j] = tmp_row[j];
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int TC;
    cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        ans = 2e9;
        cin >> row >> col >> k;
        for(int i=0; i<row; i++) for(int j=0; j<col; j++) cin >> map[i][j];
        
        /*
         k번은 체크할 필요가 없다.
         k번만큼 칠 할 수 있다면
         무조건 답이 될 수 있기 때문이다.
         그러므로 k-1번까지만 dfs를 돌면서 체크한다.
         */
        for(int i=0; i<k; i++){
            dfs(0,i);
            if( ans == 1 ){
                ans = i;
                break;
            }
        }
        if(ans == 2e9)
            ans = k;
        cout << "#" << tc << " " << ans << endl ;
    }
    return 0;
}

int tmp_row[20];
for(int i=st_row; i<row; i++){ // [1]
    for(int j=0; j<col; j++) tmp_row[j] = map[i][j];
    dfs(i+1,cnt);
    
    for(int j=0; j<col; j++) map[i][j] = 0;
    dfs(i+1,cnt-1);
    
    for(int j=0; j<col; j++) map[i][j] = 1;
    dfs(i+1,cnt-1);
    
    for(int j=0; j<col; j++) map[i][j] = tmp_row[j];
    }

#include <iostream>
#include <memory.h>
using namespace std;
#define mod 600000
 
struct p {
    int x, cnt, idx;
};
 
int arrs[mod][20], D, W, K;
p q[mod];
 
bool check(int arr[20]) {
    int tt = (1 << K) - 1, f;
    for (int i = 0; i < W; ++i) {
        f = 0;
        for (int j = 0; j <= D - K; ++j) {
            int temp = arr[i] & (tt << j);
            if (temp == (tt << j) || temp == 0) {
                f = 1;
                break;
            }
        }
        if (!f) return false; 
    }
    return true;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    register int t, a[20], i, j;
    register int aidx, qs, qe;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        memset(a, 0, sizeof(a));
        cin >> D >> W >> K;
        for (i = 0; i < D; ++i) for (int j = 0; j < W; ++j) {
            int temp;
            cin >> temp;
            a[j] = (a[j] << 1) | temp;
        }
        for (i = 0; i < W; ++i) arrs[0][i] = a[i];
        qs = qe = aidx = 1;
         
        cout << "#" << tc << " ";
        if (check(arrs[0])) {
            cout << "0\n";
        }
        else {
            int maxp = 1 << D, f = 1, ans = K;
             
            for (i = 1; i < maxp; i <<= 1) {
                int nx = i;
                 
                for (j = 0; j < W; ++j) arrs[aidx][j] = a[j] & ~i;
                if (check(arrs[aidx])) {
                    ans = 1;
                    break;
                }
                if (!(nx & 1)) {
                    q[qe++] = { nx,1,aidx };
                    aidx++;
                }
                for (j = 0; j < W; ++j) arrs[aidx][j] = a[j] | i;
                if (check(arrs[aidx])) {
                    ans = 1;
                    break;
                }
                if (!(nx & 1)) {
                    q[qe++] = { nx,1,aidx };
                    aidx++;
                }
            }
 
            while (qs<qe && f) {
                int x = q[qs].x;
                int cnt = q[qs].cnt;
                int idx = q[qs++].idx;
                 
                if (cnt != K - 1) {
                    for (i = (x&-x) >> 1; i; i >>= 1) {
                        int nx = x | i;
                        for (j = 0; j < W; ++j) arrs[aidx][j] = arrs[idx][j] & ~i;
                        if (check(arrs[aidx])) {
                            ans = cnt + 1;
                            f = 0;
                            break;
                        }
                        if (!(nx & 1)) {
                            q[qe++] = { nx,cnt + 1,aidx };
                            aidx++;
                        }
                        for (j = 0; j < W; ++j) arrs[aidx][j] = arrs[idx][j] | i;
                        if (check(arrs[aidx])) {
                            ans = cnt + 1;
                            f = 0;
                            break;
                        }
                        if (!(nx & 1)) {
                            q[qe++] = { nx,cnt + 1,aidx };
                            aidx++;
                        }
                    }
                }
                else break;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

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

int ans;
int MAP[13][20];
int r,c,k;

// 세로로 체크하는 로직 정리해두기
bool chkCondition(int (*map)[20]){
    for(int i=0; i<c; i++){
        bool chk = false;
        for(int j=0; j<r; j++){
            int continue_cnt = 1;
            for(int s=1; j+s<r && s<k; s++){
                if(map[j][i] != map[j+s][i]){
                    break;
                }
                continue_cnt ++;
            } // end of for s
            if(continue_cnt == k){
                chk = true;
                break;
            }
        } // end of for j
        // 해당 Column의 조건을 충족시키지 못했기 때문에 return false;
        if(!chk)
            return false;
    } // end of for i
    return true;
}

int dfs(int (*map)[20],int r_idx, int k_cnt){
    if( ans < k_cnt ) return ans; // ans 보다 k_cnt가 크면 약을 더 많이 사용한것이기 때문에
    if( chkCondition(map) ) return ans = ans > k_cnt ? k_cnt : ans;
    if( k_cnt >= k || r_idx >= r) {
        if( chkCondition(map) )
            return ans = ans > k_cnt ? k_cnt : ans;
        else
            return 2e9;
    }
    
    int origin_map[13][20];
    for(int i=0; i<c; i++) origin_map[r_idx][i] = map[r_idx][i];
    
    // 해당 Row를 0으로 초기화
    for(int i=0; i<c; i++) map[r_idx][i] = 0;
    dfs(map,r_idx+1,k_cnt+1);
    
    // 해당 Row를 1으로 초기화
    for(int i=0; i<c; i++) map[r_idx][i] = 1;
    dfs(map,r_idx+1,k_cnt+1);
    
    // 해당 Row에 칠하지 않고 Pass
    for(int i=0; i<c; i++) map[r_idx][i] = origin_map[r_idx][i];
    dfs(map,r_idx+1,k_cnt);
    
    return ans;
}

int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        ans = 2e9;
        memset(MAP,0,sizeof(MAP));
        cin >> r >> c >> k;
        
        for(int i=0; i<r; i++) for(int j=0; j<c; j++) scanf("%d",&MAP[i][j]);
        
        dfs(MAP,0,0);
    
        printf("#%d %d\n",tc, ans);
    } // end of for tc
    return 0;
}

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

int r,c,k;
int map[14][21];

bool dfs(int map[14][21], int initLine, int depth){
    int _map[14][21];
    if( depth == 0){ // [1]
        for(int a=1; a<=r; a++) for(int b=1; b<=c; b++) _map[a][b] = map[a][b];
        
        // 열마다 k만큼 연결되는지 체크
        bool chk = true;
        for(int a=1; a<=c && chk; a++){
            int cnt = 1;
            for(int b=1; b<=r-1; b++){
                if( _map[b][a] == _map[b+1][a]){
                    cnt ++ ;
                    if( cnt == k)
                        break;
                }
                else
                    cnt = 1;
            }
            if( cnt != k )
                chk = false;
        }
        return chk;
    } // End of [1]

    for(int i=initLine; i<=r; i++){ // [2]
        for(int a=1; a<=r; a++) for(int b=1; b<=c; b++) _map[a][b] = map[a][b];
        
        
        for(int j=1; j<=c; j++) _map[i][j] = 0;
        if(dfs(_map, i+1, depth-1))
            return true;
        
        for(int j=1; j<=c; j++) _map[i][j] = 1;
        if(dfs(_map, i+1, depth-1))
            return true;
    } // End of [2]
    
    return false;
}


int main(){
    int tc;
    cin >> tc;
    
    // c : 세로
    // r : 가로
    for(int i=1; i<=tc; i++){ // [0]
        memset(map, 0, sizeof(map));
        cin >> r >> c >> k;
        
        for(int a=1; a<=r; a++)
            for(int b=1; b<=c; b++)
                scanf("%d",&map[a][b]);
     
        int _min = k;
        for(int v=0; v<=k && v <= _min; v++)
            for(int j=1; j<=c; j++)
                if(dfs(map,j,v)){
                    _min = v;
                    break;
                }
        printf("#%d %d\n", i, _min);
    } // End of [0] Loop
    return 0;
}