[SWEA] 2112. 보호 필름

문제 접근

1. 시뮬레이션 (완전탐색) 문제이다.

2. 성능 테스트를 통과하면 현재 사용한 약품 개수가 최소인지 확인한 뒤 탐색을 종료한다.
   그렇지 않을 경우, 현재 위치(d)에 약품처리를 한 뒤 탐색을 계속한다.
   약품처리를 하기 전 상태 복구를 위해 현재 상태를 저장해야 한다.(pre 배열)
   처리가 끝난 후 저장해둔 값으로 상태를 복구해준다.

3. dfs 함수의 인자는 현재 약품처리를 할 행(d), 사용한 약품의 개수(k), 보호필름 정보(map)이다.

4. 테스트 통과 조건은 보호 필름의 모든 열(w)에 동일한 셀이 K개 이상 연속되게 존재하는 것이다.
   이해하기는 쉬웠으나 코드로 구현하기 조금 까다로웠다.

5. 완전 탐색을 끝까지 진행했을 때 문제는 풀렸으나 시간초과가 떴다.
   최소 약품의 개수를 구하는 문제이기 때문에 k개의 약품을 사용했을 때 테스트를 통과한 경우, k+1개의 약품에 대해서는 탐색하지 않도록 했다. (is_pass)
   그 결과 불필요한 탐색을 하지 않음으로써 시간초과 문제를 해결할 수 있었다.

풀이

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

int T, D, W, K, rst;
bool is_pass;
int map[14][21];

void input(){
    cin >> D >> W >> K;
    for(int i = 1; i <= D; i++){
        for(int j = 1; j <= W; j++){
            cin >> map[i][j];
        }
    }
    rst = INT_MAX;
    is_pass = false;
}

int test_pass(int map[][21]){
    for(int w = 1; w <= W; w++){
        int cnt = 1;
        bool flag = false;
        for(int d = 1; d <= D-1; d++){
            if(map[d][w] == map[d+1][w]) cnt++;
            else cnt = 1;
            if(cnt == K){ flag = true; break; }
        }
        if(!flag) return false;
    }
    return true;
}

void change(int d, int state, int map[][21]){
    for(int w = 1; w <= W; w++){
        map[d][w] = state;
    }
}

void dfs(int d, int k, int map[][21]){
    if(is_pass && k > rst) return;
    int pre[21];
    if(test_pass(map)){
        rst = min(rst, k);
        is_pass = true;
        return ;
    }
    
    for(int i = d; i <= D; i++){
        for(int w = 1; w <= W; w++) pre[w] = map[i][w]; // save
        change(i, 0, map); // A
        dfs(i + 1, k + 1, map);
        change(i, 1, map); // B
        dfs(i + 1, k + 1, map);
        for(int w = 1; w <= W; w++) map[i][w] = pre[w]; // restore
    }
}

void solve(){
    for(int i = 1; i <= D; i++){
        dfs(i, 0, map);
    }
}

int main(){
    cin >> T;
    for(int tc = 1; tc <= T; tc++){
        input();
        solve();
        cout << "#" << tc << " " << rst << endl;
    }
}