[DFS] SWEA2112 보호 필름

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE

 

Solution

• 완전 탐색으로, 총 D 개의 두께에 A, B, N(투여 안함)을 순차적으로 넣어 보면서 test 통과하는지 확인한다.

Point

• 필름의 각 층에 약품 투여를 A, B, N(안함) 중 하나를 할당하는 순열처럼 보고 test를 진행해 나간다.
• DFS 탐색 후 backtrack할 때 inject 했던 약품을 rollback 해줘야 한다.
• 가지치기(return) 조건이 어려웠는데, 우선 depth를 넘어가는 경우 return해줘야 하고, test를 통과한 경우 이 후 뒤에 약품 투여 여부와 상관 없이 해당 가지에서의 최솟값은 이미 찾은 것이므로 return 해줬다. 이 때, 주의할 것이 반드시 rollback을 하고 return 해야한다.
• 약품 투여 횟수는 dfs 함수로 넘겨서 투여할 때마다 증가시켰다.

---

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int T, D, W, K;
bool f[13][20]; //[D][W]
int ch[3] = {-1, 0, 1};//no, A, B
int result = 30;

void init() {
    result = 30;
    memset(f, 0, sizeof(f));
}

void input() {
    cin >> D >> W >> K;
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < W; j++) {
            cin >> f[i][j];
        }
    }
}

bool test() {
    for (int j = 0; j < W; j++) {
        int count = 1;
        bool prev = f[0][j];
        for (int i = 1; i < D; i++) {
            if (f[i][j] == prev) {
                count++;
                if (count == K)
                    break;
            }
            else
                count = 1;
            prev = f[i][j];
        }
        if (count < K)
            return false;
    }
    return true;
}

void inject(int d, int c) {
    if (c > -1)
        memset(f[d], c, sizeof(f[d]));
}

void printFilm() {
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < W; j++) {
            cout << f[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

void dfs(int d, int nInject) {
    if (d == D)
        return;
    
    for (int i = 0; i < 3; i++) {
        bool tmp[20];
        memcpy(tmp, f[d], sizeof(f[d]));

        int cx = ch[i];

        inject(d, cx); //inject row d with cx (-1 or 0 or 1)
        if (test()) {
            if (cx > -1)
                result = min(nInject + 1, result);
            else
                result = min(nInject, result);
            memcpy(f[d], tmp, sizeof(f[d])); //rollback injected row
            return;
        }

        if (cx > -1) //inject case
            dfs(d + 1, nInject + 1);
        else
            dfs(d + 1, nInject);
        
        memcpy(f[d], tmp, sizeof(f[d])); //rollback injected row
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int t = 1; t <= T; t++) {
        init();
        input();
        dfs(0, 0);
        cout << "#" << t << " " << result << endl;
    }
}