[C++] SWEA 2112 - 보호 필름

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

SW Expert Academy

<풀이>

1. 각 열마다 어떤 약품을 투입할 것인지 결정한다.

2. 결정된 약품을 각 열에 투입하고, 성능검사를 한다.

3. 성능검사에 통과된 약품 투입횟수 중 최솟값을 출력한다.

 

<해법>

1. 각 열마다 어떤 약품을 투입할 지 결정하는 방법.

=> 각 열마다 약품을 투입할 수 있는 모든 경우의 수를 고려해야 합니다. 저는 모든 경우의 수를 고려하는 방법으로 '백트래킹'이 있는데, 저는 재귀함수로 구현하였습니다. 저는 구현하기 이전에 아래와 같은 그림으로 큰 틀을 잡습니다.

#include <iostream>
#include <cstring>
using namespace std;
 
int D, W, K;
int map[13][20];
int tmpMap[13][20];
int medicine[13];
int res;
 
void go(int index, int medicineCnt) {
 
    //사용한 약품 개수는 합격 기준보다 많을 경우 -> 탐색 필요X
    if (medicineCnt > K) {
        return;
    }
 
    //결과값보다 많은 약품을 사용할 경우 -> 탐색 필요X
    if (res >= 0 && medicineCnt > res) {
        return;
    }
 
    //약품 선택 완료 -> 종료조건
    if (index == D) {
        
        memcpy(tmpMap, map, sizeof(tmpMap));
 
        //약품 투입
        for (int i = 0; i < D; i++) {
            if (medicine[i] == -1) {
                continue;
            }
            for (int j = 0; j < W; j++) {
                tmpMap[i][j] = medicine[i];
            }
        }
 
        //보호필름 검사
        bool isAble = true;
        //각 열마다 행 탐색
        for (int i = 0; i < W; i++) {
            int cnt = 1;
            for (int j = 0; j < D - 1; j++) {
                
                //다음 행과 비교
                if (tmpMap[j][i] == tmpMap[j + 1][i]) {
                    cnt++;
                }
                else {
                    cnt = 1;
                }
 
                if (cnt == K) {
                    break;
                }
            }
 
            if (cnt < K) {
                isAble = false;
                break;
            }
        }
 
        //결과 저장
        if (isAble) {
            if (res == -1 || medicineCnt < res) {
                res = medicineCnt;
            }
        }
 
        //종료
        return;
    }
 
    //medicine[index] -> index열에 어떤 약품이 칠해지는지 저장
    //-1 : 약품X, 0 : A약품, 1 : B약품
    for (int i = -1; i <= 1; i++) {
        medicine[index] = i;
        if (i == -1) {
            go(index + 1, medicineCnt);
        }
        else {
            //약품을 칠한 경우, 사용한 약품 개수 + 1
            go(index + 1, medicineCnt + 1);
        }
    }
    return;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        memset(medicine, 0, sizeof(medicine));
        res = -1;
 
        //입력
        cin >> D >> W >> K;
        for (int i = 0; i < D; i++) {
            for (int j = 0; j < W; j++) {
                cin >> map[i][j];
            }
        }
 
        //약품 칠하고 보호필름 검사(재귀함수)
        go(0, 0);
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
 
    return 0;
}

 

백트래킹에 대해 알아볼 수 있는 문제였습니다.