[ SWEA 2115 ] 벌꿀 채취 (C++)

SWExpertAcademy의 벌꿀채취(2115) 문제이다.

[ 설명이 굉장히 길어요. 설명을 보면서 코드를 같이 보고싶으신 분들은 밑의 코드를 자신의 개발환경에 복붙 후

  같이 켜놓고 읽으시기 바랍니다. ]

[ 문제풀이 ]

1) 문제가 조금 까다로운 면이 있는 것 같다. 천천히 하나하나 해결해 나가보도록 하자.

    먼저, 2명의 일꾼이 꿀을 채취하는데, 연속된 M개만큼의 벌통을 채취할 수 있다.

    또한  2명의 일꾼은 같은 벌통을 중복적으로 구할 수가 없다.

    그렇다면 이 상황을 그림을 통해서 알아가보자.

    이러한 맵이 있다고 생각해보자. M = 2라고 가정하겠다.

    편하게 그림을 2개씩 한번 묶어보자. 제가 해오겠습니다

    이 그림을 보고 이상하다고 느낄 수 있는데 그거 맞다. 정말 본인 마음대로 묶은 한 경우일

    뿐이다. 문제를 풀 때에는 이런 경우가 아닌, 첫째줄에 (2, 3)으로 벌통을 채취할 수도 있고 그런 경우들이 많이 있다.

    쉬운 설명을 위해서 위와 같은 예를 들고 왔을 뿐이다.

    그렇다면 이 상태에서 1번 사람이 (1) 번 벌통 2개를 채취했다고 생각해보자. 그렇다면 2번 사람에게 남은 선택권은

    무엇일까 ???

    2, 3, 4, 5, 6, 7, 8 중에 하나일 것이다. 이를 { 1번사람 , 2번사람 } 으로 나열해보면

    { 1, 2 }, { 1, 3 }, { 1, 4 }, { 1, 5 }, { 1, 6 } , {1, 7 }, { 1, 8 } 이 된다.

    그렇다면 위의 7가지 경우에 대해서 문제에 맞게 계산을 했다고 가정하자.

    그렇다면 1번사람이 2번 벌통을 채취했다고 생각해보면 어떻게 될까 ???

    { 2, 3 }, { 2, 4 } .... { 2, 8 }이 될것이다. 왜 { 2, 1 }은 안될까? 사실 된다. 안될이유가 전혀 없다. { 2, 1 }도 된다.

    그런데... 여기서 한번 생각을 해보자.

    1번 사람이 1번 벌통들을 채취하는 것 + 2번 사람이 2번 벌통들을 채취하는 것과

    1번 사람이 2번 벌통들을 채취하는 것 + 2번 사람이 1번 벌통들을 채취하는 것.

    이 2가지 경우가 계산 값이 달라질까??? 그럴리없다. 절대 달라지지 않는다. 즉, { 1, 2 } 에서 이미 계산한 결과이기 떄문에

    우리는 불필요하게 { 2, 1 } 을 계산을 할 필요가 없다는 것이다. 이는 시간낭비일 뿐이다.

    그렇다면 1번 사람이 3번 벌통 채취한 걸로 가보자.

    아마 결과가 { 3, 4 } , { 3, 5 } ... { 3, 8 } 이 나올 것이다. 이 쯤 되면 눈치를 채야한다.

    2명의 사람이 벌통을 채취하는 것을 고르는 것은 ' 조합 ' 이라는 것이다.

    순열이 아닌 조합인 이유에 대해서도 위에서 말을 했다.

    아직 조합 구현하는 법을 잘 모른다면 아래의 글을 읽고 오도록 하자.

    [ 조합 구현하는 법 알아보기(Click) ]

   

    그런데 이 문제는 사실 조합 구현하는 법을 알았다고 해도 약간 까다로운 부분이 있다. 단순 1차원적인 배열수준에서

    뽑는 것이 아닌 2차원 맵에서 뽑아줘야 하기 때문이다. 이 부분을 자세하게 알아보자.

    먼저 본인은 뽑기전에, 이 벌통을 뽑을 수 있나? 부터 체크를 해 주었다.

    이 체크 하는 것은 총 2가지를 확인한다.

    1. 현재 좌표부터 + M 칸 까지 모두 이전에 뽑힌적이 없는 좌표들인지?

    2. 현재 좌표부터 + M 칸 까지 모두 맵의 범위 내에 존재하는지.

    즉, 아래와 같은 코드로 이 부분을 구현할 수 있다.

bool Can_Select(int x, int y)    //(x,y)는 현재 좌표
{
    for (int j = y; j < y + M; j++)
    {
        if (Visit[x][j] != 0 || j >= N) return false;
    }
    return true;
}   

    이 조건을 만족해야 뽑을 수 있는 벌통이 된다. 또한 한가지 유의할 것은, Visit[][] 배열을 일반적인 bool형이 아닌

    int형으로 선언해 주었다는 점이다. int형으로 선언한 이유는 1번사람이 채취한 벌통과 2번사람이 채취한 벌통을 구분하기

    위해서이다. 즉, Visit[x][y] = 1 이면 1번사람이 채취한 벌통이라는 것을 의미하고 = 2 이면 2번사람이 채취한 벌통이라는

    것을 의미한다.

 

    그런데 코드 세부적인 내용을 이해하는것도 중요하지만 우리가 지금 뭘하고 있는지 잘 생각해보자.

    우리는 '조합'을 통해서 사람 2명이 벌통을 채취한다는 것을 알았다. 또한, 벌통을 채취하기 위한 조건을 통과해야만

    채취할 수 있다는 것을 알았고 실제로 그걸 코드로 구현하는 것을 보았다.

    지금부터라도 어떤 단계로 진행하는지 현재 단계가 무엇을 위해서 하고있는 과정인지 확실히 하자.

    우리는 이전에 벌통을 아직 뽑은적이 없다. 이제서야 막, 벌통을 뽑기 위한 조건을 알았을 뿐이다.

    즉, 어느 한 정점에서 위의 Can_Select() 함수에서 true를 받아냈다면, 1번 사람이 그 좌표부터 +M 좌표까지의 벌통을

    갖게 될 것이다.

    이 다음 과정은 무엇일까? 당연히 2번사람이 뽑는 것이 그 과정일 것이다.

    본인은 이 과정에서 재귀 함수를 호출해 주었다.

    왜냐하면, 1번사람이 1번 벌통을 채취했을때, 2번 사람은 2, 3, 4, 5, ~~~ 번의 벌통을 채취할 수 있기 떄문이다.

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)        // 모든 정점을 돌아보면서
        {
            if (Can_Select(i, j) == true)    // 채취 가능한 곳이라면
            {
                Make_Visit(i, j, 1);        // 1번 사람이 채취했다고 표시
                Actual_Select(i, j, 1);    // 2번 사람 채취를 위한 재귀함수.
                Make_Visit(i, j, 0);        // 1번 사람 채취 표시 해제
            }
        }
    }

      

2) 이제 1번사람을 뽑았으니 2번사람이 벌통을 채취해야한다. 그러기 위해서 우리는 재귀함수를 하나 호출해 주었다.

    이 재귀함수의 종료조건은 무엇일까?? 2번 사람이 벌통을 채취하면 이제 계산하고 종료시켜 주면 된다.

    2번 사람이 뽑는 것은 위의 코드와 같은 방식으로 진행되게 된다. Can_select()함수를 통해서 뽑을 수 있는 벌통이라면

    뽑는 그런식이다. 이렇게 우리는 2차원 맵에서 조합을 구현하게 되는 것이다.

3) 이제 1번사람과 2번사람이 다 뽑았으니 이제 계산을 하면 된다.

    본인은 계산을 하기 위해서 먼저, 1번 사람이 뽑은 벌통들의 값들을 저장하는 Vector와, 2번사람이 뽑은 벌통들의

    값을 저장하는 Vector를 임시적으로 만들어 주었다.

  

    여기서 또 하나의 큰 문제가 발생한다. 뽑은 M개의 꿀의 양이 다 합쳐서 C를 넘어버리면 그 중에 또 선택을 해야한다.

    선택을 결정하는 값은 '수익'이다. 수익이 최댓값이 되는 경우를 우리는 찾아서 선택해 줘야 한다.

    M개를 모두 합쳐서 C를 넘지 않는 경우는 그냥 수익을 구하는 식으로 계산만하면 되니 별다른 설명을 하지는 않겠다.

    여기서 또 한번의 조합을 구현해 주어야 한다. 왜 또 조합???

    예를 들어서 C = 11, M = 3일 경우에 채취한 벌통이 [ 5, 6, 9 ] 라고 생각해보자.

    이 경우 5 + 6 + 9 > 11 이므로 선택을 해줘야 한다. 그런데 몇개를 선택해야될까?? 그걸 우리는 지금 알 수가 없다.

    그래도 2개를 선택하는게 더 큰 수익이 나지 않을까? 라고 생각할 수 있지만 실제로 계산해보면 그렇지 않다.

    C = 11이므로 선택할 수 있는 경우로는 [ 5 ] , [ 5, 6 ] , [ 9 ] 이런 경우에 뽑을 수가 있다.

    하지만 각각의 수익을 계산해보자. 25 , 61 , 81 이다. 2개인 [ 5, 6 ]을 뽑았을 때보다 [ 9 ] 하나만을 뽑았을 때의

    수익이 더 크게된다. 그래서 우리는 조합을 구현해야 하는데, 몇 개를 뽑아야 할지 모르는 상황이다.

    그래서 본인은 비교할 특정값을 임시적으로 만들어 주었다.

    바로 int Max_Value[2] 이다. Max_Value[0] 은 1번사람의 수익의 최댓값이, Max_Value[1]에는 2번사람의 수익의

    최댓값이 들어가게 된다. 초기값은 0이다.

    이 값을 기준으로 우리는 조합을 뽑게된다. 조합을 뽑는 DFS함수의 매개변수는 총 5개를 사용해주었다.

    DFS(vector , int Idx, int IIdx, int Total, int Benefit)

    먼저 가장 앞에 vector는 1번 사람과 2번사람이 뽑은 꿀의 양을 저장해놓는 Vector이고 Idx는 1번사람과 2번사람을

    구분하기 위한 변수, IIdx는 조합을 뽑기 위해서 사용되는 변수, Total은 꿀의 채취양, Benefit은 수익이다.

    DFS의 return 조건은 딱 하나이다. 바로 Total 값이 C보다 큰 경우 !

    코드와 주석을 통해 이해해보자.

void DFS(vector<int> V, int Idx, int IIdx, int Total, int Benefit)
{
    if (Total > C) return;                                    // 선택한 꿀의 양이 C보다 크면 의미가 없는 조합이므로 return.
    if (Max_Value[Idx] < Benefit) Max_Value[Idx] = Benefit;    // 수익의 최댓값을 계속 갱신해주면서 저장.
   
    for (int i = IIdx; i < M; i++)                // 일반 조합을 뽑는 코드
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(V, Idx, i, Total + V[i], Benefit + (V[i] * V[i]));
        Select[i] = false;
    }
}

   

     위의 코드와 같이 우리는 몇 개를 뽑지 모르는 상황에서도 조건에 맞게 최대의 수익을 내는 조합을 찾아낼 수가 있다.

     정확하게 말하자면 최대의 수익을 내는 조합을 찾아낸 것이 아닌, 만들어진 조합으로 최대의 수익을 찾아낸 것이다.

    

4) 이제 다 끝났다. 위에서 구한 최대수익을 통해서 최댓값을 저장해주고 갱신해주면 된다.

    이 과정을 모든 조합에서 반복해 주는 것이다.

    1번 사람이 채취한 후에 우리는 재귀 함수를 호출했다고 하였는데 그 재귀함수에 대한 코드와 주석설명을 하고 마치겠다.

void Actual_Select(int x, int y, int Idx)        // 1번사람이 채취한 후에, 재귀호출. 즉 초기 Idx = 1로 호출이 됨.
{
    if (Idx == 2)                                    // 재귀의 종료조건. 2번 사람이 벌통을 채취하면 계산 후 종료.
    {
        Simple_Initialize();                        // 이 안에서 사용되는 변수들만 초기화
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (Visit[i][j] == 1) A_Honey.push_back(MAP[i][j]);
                else if (Visit[i][j] == 2) B_Honey.push_back(MAP[i][j]);    // 각 사람이 뽑은 꿀의 양을 Vector에 저장.
            }
        }

        if (Honey_Max(A_Honey) <= C) Max_Value[0] = Bigger(Max_Value[0], Calculate(A_Honey));

  // 가장 편한 경우. M개의 꿀의 양을 합쳐도 C보다 작으면 조합 필요없이 바로 계산

       else DFS(A_Honey, 0, 0, 0, 0);
        // 그게 아니라면 조합을 통해서 최대 수익을 구해줘야 함.

        if (Honey_Max(B_Honey) <= C) Max_Value[1] = Bigger(Max_Value[1], Calculate(B_Honey));

        else DFS(B_Honey, 1, 0, 0, 0);
        // 2번사람도 똑같이 진행
        int Temp_Answer = Max_Value[0] + Max_Value[1];    // 결과값 도출 후
        Answer = Bigger(Answer, Temp_Answer);                // 최댓값 갱신

        return;
    }

    for (int i = x; i < N; i++)        // 초기에 Idx = 1로 호출되면 여기로 오게됨.
    {
        for (int j = 0; j < N; j++)
        {
            if (Can_Select(i, j) == true)    // 선택할 수 있는 벌통을 만나게 되면
            {
                Make_Visit(i, j, 2);
                Actual_Select(i, j, 2);        // Idx = 2 로 재귀호출
                Make_Visit(i, j, 0);
            }
        }
    }
}

 

       아 그리고, 위에 코드에서 보면 가장 마지막에 Idx = 1로 호출되었을 때 오게되는 for문에서 i와 j의 범위에 대해서

       만 간략하게 설명하겠다. 보면 i = x 부터, j = 0부터 실행이된다.

       즉, x행 0열부터 벌통 탐색을 시작한다는 것이다. 왜, x행 y열부터 실행하면 안될까??

       다음과 같은 경우를 보자.

      

      여기서 M = 1일 때, 1번 사람이 제일 윗줄에 가장 오른쪽에 있는 (0, 2)에 있는 '3'을 채취했다고 생각해보자.

      그렇게 됬을 때 2번사람은 5, 6, 7, 9, 8, 7 중에 하나를 선택할 수 있는데 for문의 범위를 i = x 부터, j = y부터로 할 경우

      아마 가장 먼저 (0, 3)을 탐색하고 채취할 수 없는 벌꿀이니 i가 ++되어 x + 1인 1행을 탐색하기 시작할 것이다.

      근데 j = y부터이다. 즉, 1행 2열을 탐색할 것이다. 5와 6을 탐색을 못하고 지나치는 경우가 발생할 수 있다.

      따라서 행은 x부터 해도 되지만, j = 0부터 해야 된다는 점 주의하자.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
int Answer;
int N, M, C;
int MAP[MAX][MAX];
int Visit[MAX][MAX];
bool Select[5];
int Max_Value[2];
vector<int> A_Honey, B_Honey;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
    Max_Value[0] = Max_Value[1] = 0;
    A_Honey.clear();
    B_Honey.clear();
    memset(Select, false, sizeof(Select));
    memset(Visit, false, sizeof(Visit));
    memset(MAP, 0, sizeof(MAP));
}
 
void Simple_Initialize()
{
    Max_Value[0] = Max_Value[1] = 0;
    A_Honey.clear();
    B_Honey.clear();
    memset(Select, false, sizeof(Select));
}
 
void Input()
{
    cin >> N >> M >> C;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
bool Can_Select(int x, int y)
{
    for (int j = y; j < y + M; j++)
    {
        if (Visit[x][j] != 0 || j >= N) return false;
    }
    return true;
}
 
void Make_Visit(int x, int y, int T)
{
    for (int j = y; j < y + M; j++)
    {
        Visit[x][j] = T;
    }
}
 
int Honey_Max(vector<int> V)
{
    int Sum = 0;
    for (int i = 0; i < V.size(); i++)
    {
        Sum = Sum + V[i];
    }
    return Sum;
}
 
int Calculate(vector<int> V)
{
    int Sum = 0;
    for (int i = 0; i < V.size(); i++)
    {
        Sum = Sum + (V[i] * V[i]);
    }
    return Sum;
}
 
void DFS(vector<int> V, int Idx, int IIdx, int Total, int Benefit)
{
    if (Total > C) return;
    if (Max_Value[Idx] < Benefit) Max_Value[Idx] = Benefit;
    
    for (int i = IIdx; i < M; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(V, Idx, i, Total + V[i], Benefit + (V[i] * V[i]));
        Select[i] = false;
    }
}
 
void Actual_Select(int x, int y, int Idx)
{
    if (Idx == 2)
    {
        Simple_Initialize();
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (Visit[i][j] == 1) A_Honey.push_back(MAP[i][j]);
                else if (Visit[i][j] == 2) B_Honey.push_back(MAP[i][j]);
            }
        }
 
        if (Honey_Max(A_Honey) <= C) Max_Value[0] = Bigger(Max_Value[0], Calculate(A_Honey));
        else DFS(A_Honey, 0, 0, 0, 0);
        
        if (Honey_Max(B_Honey) <= C) Max_Value[1] = Bigger(Max_Value[1], Calculate(B_Honey));
        else DFS(B_Honey, 1, 0, 0, 0);
 
        int Temp_Answer = Max_Value[0] + Max_Value[1];
        Answer = Bigger(Answer, Temp_Answer);
 
        return;
    }
 
    for (int i = x; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Can_Select(i, j) == true)
            {
                Make_Visit(i, j, 2);
                Actual_Select(i, j, 2);
                Make_Visit(i, j, 0);
            }
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Can_Select(i, j) == true)
            {
                Make_Visit(i, j, 1);
                Actual_Select(i, j, 1);
                Make_Visit(i, j, 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;
 
}