[SW Expert 2112] 보호 필름

#문제

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

#풀이

모의 SW 역량 테스트 문제들중 하나 입니다.

역시 삼성 문제스럽게 나왔습니다.
저는 이 문제를 완탐으로 풀었습니다.
SW 역량 테스트관련 알고리즘들을 푸는지라... 계속 완탐 문제만 푸는것 같습니다......

문제 해결 방식은 다음과 같습니다.

각 막에서 약품을 안뿌리고 넘어갈 것인가? 
아니면 뿌리는데 A를 뿌릴것인가, B를 뿌릴것인가

총 3가지 길로 나누어 모든 경우의 수를 돌렸습니다.

이 때, 중요한 점이 있습니다.

완전 탐색을 하기 위해서는 그전의 film을 복사 하여야 합니다.

(이유는 그 전 알고리즘 풀이에도 많이 있습니다 -> 치킨배달 : http://jongnan.tistory.com/34)

복사할때 만약 film 전체를 복사한다고 해봅시다.
배열의 최대 크기가 13×20 이고, 재귀 호출을 돌린다면 최대 13×4번(복사를 4번 하기 때문에), 다 돌렸을 때 K를 만족하는지에 대해서도 확인을 해야하므로 엄청난 시간이 들게 됩니다.

따라서 전체 배열을 복사하는 것이 아닌 해당 막만 복사합니다.

그렇다면 시간이 확 줄겠죠? :)

검사를 통과 하는 것에 대해서는 이차원 배열을 돌면서 확인하는 것이므로 잘 하실꺼라 믿습니다!

처음에 저는 깊이를 1로 시작해서... 2번째 부터 약품을 뿌릴건지 안뿌릴건지 확인을 하는 불상사를...

그것 때문에 반례도 다 찾아봤는데 다 맞았다는... 실수를 조심합니다. :)

#코드

#include <iostream>
 
#define INF 987654321
#define W_MAX 20
#define M_MAX 13
 
using namespace std;
 
int film[M_MAX][W_MAX];
int D,W,K;
int ans;
 
void init(){
    for(int i = 0; i < M_MAX; i++){
        for(int j = 0; j < W_MAX; j++){
            film[i][j] = 0;
        }
    }
}
 
void copyfloor(int a[W_MAX], int b[W_MAX]){
    for(int i = 0; i < W; i++){
        a[i] = b[i];
    }
}
 
void spreadMedicine(int d, int kind){
    for(int i = 0; i < W; i++){
        film[d][i] = kind;
    }
}
 
//성능 시험을 통과하는지 확인
//만약 통과를 한다면 그때의 뿌린 횟수를 저장
void checkFilm(int cnt){
    for(int i = 0; i < W; i++){
        int hap = 1;
        for(int j = 0; j < D-1; j++){
            if(hap >= K){
                break;
            }
            if(film[j][i] == film[j+1][i]){
                hap += 1;
            }else{
                hap = 1;
            }
        }
        if(hap < K){
            return;
        }
    }
    if(ans > cnt){
        ans = cnt;
    }
}
 
void dfs(int d, int cnt){
    if(cnt > ans){
        return;
    }
    if(d >= D){
        checkFilm(cnt);
        return;
    }
    
    //각 층에서 약품을 뿌리거나, 안뿌리거나 둘중 하나
    //뿌릴 경우에는 A를 뿌리느냐, B를 뿌리느냐!
    
    //(1) 안뿌릴 경우
    dfs(d+1, cnt);
    
    //약품을 뿌릴 경우에는 전 상황을 저장하여 모든 경우의 수를 확인
    //(2) A를 뿌릴 경우
    int temp[W];
    copyfloor(temp, film[d]);
    spreadMedicine(d, 0);
    dfs(d+1, cnt+1);
    copyfloor(film[d], temp);
    
    //(3) B를 뿌릴 경우
    copyfloor(temp, film[d]);
    spreadMedicine(d, 1);
    dfs(d+1, cnt+1);
    copyfloor(film[d], temp);
}
 
int main(){
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++){
        init();
        cin >> D >> W >> K;
        //film 받기
        for(int i = 0; i < D; i++){
            for(int j = 0; j < W; j++){
                cin >> film[i][j];
            }
        }
        ans = INF;
        dfs(0,0);
        cout << "#" << t <<" " <<ans << endl;
    }
    return 0;
}