[SW Expert Academy] 2112번 보호 필름

문제

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

풀이

굉장히 오래 걸린 문제다. 처음 접근은 Dfs를 돌며 이차원 행렬을 넘겨주는 식으로 구현했었는데 이렇게 되면 항상 성능검사를 해야돼서 구현이 정말 복잡했다.

성능검사를 하는 구현도 복잡해서 잘 못했고 재귀함수도 올바른 방법으로 구현을 하지 못했던 것 같다.

결국엔 해설을 찾아보고 이해가 쉽게 가는 방법으로 다시 코드를 짜봤다.

일단 Dfs로 모든 행을 하나씩 돌아보며 i-1 번째 행까지의 연속된 셀의 개수를 세고 k개 이상이면 그 열의 성능검사가 통과했다는 것을 저장해서 넘겼다.

해당하는 열이 성능검사를 통과 했는지의 여부는 비트마스크를 이용해서 통과하면 1 못하면 0으로 해당하는 비트를 바꿨다.

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_D 14
#define MAX_W 21
#define MAX_INF 987654321

int T;
int d, w, k;
int film[MAX_D][MAX_W];
int check[MAX_D][MAX_W];
int now_film[MAX_D][MAX_W];
int ans = MAX_INF;

void Initialize()
{
    for (int i = 0; i < MAX_D; i++)
    {
        for (int j = 0; j < MAX_W; j++)
        {
            film[i][j] = 0;
            now_film[i][j] = 0;
            check[i][j] = 0;
        }
    }
}

int update(int row, int m, int msk)
{
    for (int i = 1; i <= w; i++)
    {
        int cur = m == -1 ? film[row][i] : m;

        if (now_film[row - 1][i] == cur)
            check[row][i] = check[row - 1][i] + 1;
        else
            check[row][i] = 1;

        now_film[row][i] = cur;

        // 연속된 셀의 개수가 k개 이상되면 해당 열의 성능 검사 통과를 저장한다.
        if (check[row][i] >= k)
            msk |= (1 << (i - 1));
    }

    return msk;
}

void Dfs(int row, int cnt, int msk)
{
    // 약품 투입을 저장 된 ans값보다 많이 하는 경우는 그냥 종료
    if (cnt >= ans) return;

    // 모든 검사가 끝났고 성능 검사를 통과하면 저장
    if (row == d + 1)
    {
        if (msk == (1 << w) - 1) ans = cnt;
        return;
    }

    // -1 : 투여 X, 0 : A 투여, 1 : B 투여
    for (int i = -1; i < 2; i++)
    {
        Dfs(row + 1, cnt + (i == -1 ? 0 : 1),
            update(row, i, msk));
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;

    for (int test_case = 1; test_case <= T; test_case++)
    {
        Initialize();

        cin >> d >> w >> k;

        for (int i = 1; i <= d; i++)
        {
            for (int j = 1; j <= w; j++)
            {
                cin >> film[i][j];
            }
        }

        ans = MAX_INF;

        Dfs(1, 0, 0);

        cout << "#" << test_case << " " << ans << "\n";

    }

    return 0;
}