[ SWEA 2112 ] 보호 필름 (C++)

SWExpertAcademy의 보호필름(2112) 문제이다.

[ 문제풀이 ]

먼저, 구현하기 앞서 어떻게 접근해야 할지에 대해서 부터 알아보자.

이 문제는 행에 약물을 투여해 가면서, 모든 열이 동일한 특성을 지닌 셀이 K개 이상 연속적으로 존재하도록

만들어 주어야 하는 문제이다.

그럼 몇 번째 행에, 무슨 약물을 투여할지에 대해서 생각을 해보자.

본인은 특정 행에 약물을 투여하는 과정을 조합으로 구현해 보았다.

지금부터 왜 조합을 구현했는지 알아보자.

(지금부터 '막' 이라는 표현이 나오는데, 문제에서도 '행'을 '막'이라고 표현해서 '막'이라고 표현했습니다 !

 '막' = '행' )

문제에 설명으로 나와있는 예시를 한번 봐보자. 문제 설명의 [Fig. 4] 에서, "3번째 막을 A로, 6번째 막을 B로" 변경하니

성능검사를 통과할 수 있다 라고 해놨다.

그럼 3번 막을 변경하고, 그 이 후에 6번 막을 변경하는 것과 6번막을 변경하고, 그 이후에 3번 막을 변경하는 것과

결과가 달라질까??

아니다 결과가 같을 것이다. 즉 ! 몇 번째 막을 먼저 선택하는지, 나중에 선택하는지에 따라서 결과가 달라지지 않는다.

결과적으로 "약물을 투여할 막(행)을 선택하는데 있어서 순서는 결과에 영향을 미치지 못한다"

따라서, 순열이 아닌 조합을 구현한 것이다.

아직 조합에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 조합 바로가기(Click) ]

하지만 ! 조합을 구현할 때 단순히 "x번 막을 선택했습니다 , 안했습니다" 로는 부족하다.

왜냐하면 선택한 막에 무슨 약물을 투여할지도 결정을 해줘야 하기 때문이다.

문제를 제대로 파악하지 못해서 그런건지, 문제의 테스트케이스가 부족해서 그런건지는 잘 모르겠지만, 사실,

여러 개의 막을 선택해놓고 선택한 막들을 모두 동일한 특성으로 바꿔주더라도 pass를 받을 수 있다.

본인도 처음에 구현할 때 실수를 해서 잘못 구현해놓고 pass를 받아서 맞은 줄 알았다.

( 본인도 위에서 말한 경우처럼 구현하더라도, 왜 pass를 받을 수 있는지 정확한 이유는 잘 모르겠습니다 ! )

다시 본론으로 돌아와보자. 그래서 본인은 특정 막을 선택하게 되면, 해당 막을 순차적으로 A특성과 B특성을 넣어보는

식으로 구현해 보았다. 코드로 보자면 다음과 같이 구현했다.

void DFS(int Idx, int Cnt)
{
    for (int i = Idx; i < D; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        for (int j = 0; j < 2; j++)
        {
            Make_Visit(i, j, true);
            DFS(i, Cnt + 1);
            Make_Visit(i, j, false);
        }
        Select[i] = false;
    }
}

조합을 구현하는 코드와 비슷한데, 단순 Select로 선택했음, 안했음만 표시해주는 것이 아니라, 선택을 하게 되면

line7) 에 존재하는 for문에 의해서 약물을 A특성, B특성 순차적으로 투여 해보도록 구현했다.

즉, 일반적인 조합처럼 "a번 데이터를 선택했으면, 그 다음 데이터를 선택하는 과정으로 넘어가는 것이 아니라, a번 데이터를

어떤 약물로 바꿀지까지 정한 후, 그 다음 데이터를 선택하는 과정으로 넘어가게 되는 것" 이다.

그럼, 이 조합의 종료조건은 어떻게 될까 ? 보통 조합의 경우 원하는 갯수만큼 선택을 하게 되면, 종료를 하게 된다.

하지만, 이 경우에는 선택해야 할 정해진 갯수가 존재하지 않는다.

따라서, 본인은 '무엇이라도 선택했다면' 문제의 조건을 만족하는지 체크하고 기존의 답과 비교하여 갱신해 주었다.

void DFS(int Idx, int Cnt)
{
    if (Check(C_MAP) == true)
    {
        Answer = Min(Answer, Cnt);
        return;
    }
    
    for (int i = Idx; i < D; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        for (int j = 0; j < 2; j++)
        {
            Make_Visit(i, j, true);
            DFS(i, Cnt + 1);
            Make_Visit(i, j, false);
        }
        Select[i] = false;
    }
}

이런식으로, Check() 함수를 하나 만들어서, DFS 함수가 호출 될 때 마다, Check() 해서 확인해 주었다.

하지만 이렇게만 구현할 경우 시간초과를 받게 된다.

그래서 본인은 '더 이상 탐색해도 되지 않아도 되는' 2가지 조건을 더 달아주었다.

먼저 첫 번째는 기존의 투여한 약물의 갯수보다 더 많다면 더 이상 탐색을 진행하지 않아도 되게 만들어 주었다.

만약, 내가 약물을 2개의 막에 투여해서 현재 까지의 최소 횟수가 '2'인데, 지금 탐색하는데 약물을 투여한 횟수가 3회 이상이라

면, 이 경우가 정답이 될 가능성이 있을까 ?? 가능성이 절대 없다.

두 번째는, 약물을 투여한 횟수가 K번 이상이라면 더 이상 투여하지 않도록 만들어 주었다.

왜냐하면, 우리는 모든 열들의 셀이 K개 이상 연속적으로 존재하도록 만들어야 하는데, K번 이상 투여할 필요가 없기

때문이다.

예를 들어서, K = 5 일 때, 최악의 경우를 생각해보면, 5개의 연속된 행을 모두 동일한 특성으로 바꿔주면 문제의 조건을

만족할 수 있기 때문에, 약물을 투여한 횟수가 K번을 넘는다는 것은 절대로 최소횟수가 아닌 경우인데도 끝까지 탐색을

하고 있다는 말이 된다.

이렇게 2가지 조건을 더 달아주니 pass를 받을 수 있었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int D, W, K, Answer;
int MAP[MAX][MAX];
int C_MAP[MAX][MAX];
bool Select[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Answer = 987654321;
    memset(Select, false, sizeof(Select));
}
 
void Input()
{
    cin >> D >> W >> K;
    for (int i = 0; i < D; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> MAP[i][j];
            C_MAP[i][j] = MAP[i][j];
        }
    }
}
 
bool Check(int Arr[][MAX])
{
    for (int i = 0; i < W; i++)
    {
        int A_Cnt = 0;
        int B_Cnt = 0;
        bool Flag = false;
 
        for (int j = 0; j < D; j++)
        {
            if (Arr[j][i] == 0)
            {
                B_Cnt = 0;
                A_Cnt++;
            }
            else
            {
                A_Cnt = 0;
                B_Cnt++;
            }
 
            if (A_Cnt == K || B_Cnt == K)
            {
                Flag = true;
                break;
            }            
        }
        if (Flag == false) return false;
    }
    return true;
}
 
void Make_Visit(int Idx, int Value, bool T)
{
    if (T == true)
    {
        for (int i = 0; i < W; i++)
        {
            C_MAP[Idx][i] = Value;
        }
    }
    else
    {
        for(int i = 0; i < W; i++)
        {
            C_MAP[Idx][i] = MAP[Idx][i];
        }
    }
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt > K || Cnt >= Answer) return;
    if (Check(C_MAP) == true)
    {
        Answer = Min(Answer, Cnt);
        return;
    }
    
    for (int i = Idx; i < D; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        for (int j = 0; j < 2; j++)
        {
            Make_Visit(i, j, true);
            DFS(i, Cnt + 1);
            Make_Visit(i, j, false);
        }
        Select[i] = false;
    }
}
 
void Solution()
{
    if (Check(MAP) == true || K == 1)
    {
        Answer = 0;
        return;
    }
    DFS(0, 0);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}