[ SWEA 2105 ] 디저트 카페 (C++)

SWExpertAcademy의 디저트카페(2105) 문제이다.

( 설명이 굉장히 길어요.. )

[ 문제풀이 ]

1) 문제를 해결하는 가장 큰 틀을 먼저 설명하자면, 현재 좌표에서 갈 수 있는 4가지 방향에 대해서 갈 수 있는 조건에 부합하는

   좌표라면(중복되지 않은 디저트 , 방문하지 않은 좌표) 방문해보고 최대값을 갱신하는 식으로 구현할 수 있다.

   이 부분을 본인은 재귀를 통해서 모든 경우를 다 탐색해보는 깊이 우선 탐색법인 DFS를 이용해서 구현해보았다.

   이렇게 구현할 경우 pass를 받는데는 아무런 문제가 없다. 다만, 시간이 조금 오래 걸릴 뿐이다.

   그래서, 문제를 해결하는 방법을 설명하기 전에 시간이 왜 오래걸리는지 그리고 어떻게 해야 이 시간을 조금이라도

   줄일 수 있는지에 대해서 부터 설명을 하고 구체적인 풀이 방법으로 들어가보도록 하자.

   ( 시간이 오래걸리더라도 pass만 받으면 된다 ! 하시는 분들은 2)번으로 바로 넘어가셔도 무관합니다.

    다시 말하지만, 모든 경우를 다 탐색하는 방법으로 하더라도 pass를 받는 데 문제가 없습니다. )

  

   위와 같은 맵을 예시로 생각해보자. 맵의 가장 왼쪽 위 좌표를 (0, 0) 이라고 했을 때, (0, 1)에서 시작해서 저런 주황색

   사각형을 만들었다고 생각해보자. 사각형을 다음과 루트를 통해서 만들었다고 생각해보자.

   8 (0, 1) → 9 (1, 2) → 7 (2, 1) → 4 (1, 0) → 8 (0, 1) 이러한 루트를 통해서 만들어졌다고 생각해보자.

   그렇다면, 이제 시작점을 (0, 1)이 아닌 (1, 2)에 존재하는 9 라고 생각해보자.

   시작점이 (1, 2)일 때, 위와 같은 사각형이 그려질 수 있을까 ?? 전혀 문제없이 그려질 수 있다. 하지만 ! 이미 한번 그려진

   중복된 사각형 이라는 것을 알 수가 있다. (0, 0)부터 (N -1, N-1)까지 순차적으로 탐색한다고 했을 때, 분명히

   (0, 1)을 시작점으로 한번 그려진 사각형이 될 것이다.

   그렇다면 이번에는 시작점을 (2, 1)인 7이라고 생각해보자. 마찬가지로 위의 사각형을 그리는데 문제가 없다는 것을

   알 수 있다. 하지만, 이미 8에서도 한번, 9에서도 한번나온 사각형이라는 것이다.

   이러한 부분 때문에 시간이 오래 걸리는 것이다. 현재 정점으로부터 갈 수 있는 모든 방향으로 탐색을 하게 되면

   중복된 사각형을 계속해서 탐색하는 경우가 발생하게 된다.

  

   그럼 지금부터는 이렇게 중복되는 사각형을 조금이라도 줄일 수 있는 방법에 대해서 알아보자.

   본인은 모든 좌표에서 탐색을 하되, 탐색의 시작 방향을 움직일 수 있는 4가지 방향 모두에 대해서 하지 않고,

   무조건 "오른쪽 아래"로 탐색을 시작하도록 설정해 주었다.

   무조건 오른쪽 아래로 하면 위의 그림에 그려진 주황색 사각형은 (0, 1)에서 탐색을 시작할 경우에만 나오게 되고

   (1, 0), (1, 2), (2, 1)에서 시작하게 되면 위와 같은 사각형을 그릴 수 없게 된다.

   자연스럽게 중복된 사각형에 대한 탐색을 이전의 방식에 비해서 줄어들게 될 것이다. 그런데 ! 이게 무조건 정답이

   될 수 있을까 가 문제이다. 분명히, 오른쪽 아래가 아닌 다른 방향으로 탐색을 시작했을 때 정답이 나오는 경우가

   존재하지 않을까 ??

   그렇다면 아래의 3가지 예시를 보고 판단해보자.

  

    빨간점을 시작점이라고 생각했을 때, 그려질 수 있는 사각형을 그려본 것이다.

    우리가 생각해봐야 할 것은 "오른쪽 아래로 탐색을 시작하지 않았을 때, 정답이 나올 수 있는가 ?" 이다.

    위의 3가지 경우는 모두 오른쪽 아래로 탐색을 시작하지 않는 경우이다. 즉, 위와 같은 경우에서 정답이 나오지는

    않을지 생각해보자. 딱 보면 알겠지만 위의 그림은 아래의 그림과 같이 이미 중복된 사각형임을 알 수 있다.

   

     바로 위의 그림의 시작점에서 오른쪽 아래로 탐색을 시작했을 경우 나올 수 있는 사각형이라는 것이다.

     정리를 해보자면, 무조건 "오른쪽 아래방향으로 탐색을 시작" 하더라도 정답을 구하는데는 문제가 없음을 알 수 있다.

     이런식으로 탐색을 시작하게 된다면 시간을 조금 줄일 수 있을 것이다.

     그렇다면 우리는 자연스럽게 또 하나의 처리해야할 경우를 알 수 있다. 가장 오른쪽 열(N - 1열) 은 탐색을 해볼 필요가

     있을까?? 위에서 말한대로 탐색을 무조건 오른쪽 아래방향으로만 시작을 할 건데, 가장 오른쪽 열의 오른쪽 아래 방향은

     맵의 범위를 벗어난 곳이다. 자연스럽게 볼필요도 없다는 것이다.

     또 하나는 0 열(가장 왼쪽 열) 또한 볼 필요가 없다는 것이다. 0열같은 경우에는 오른쪽 아래 좌표가 맵의 제 범위일 수도

     있는데 왜 확인해보지 않아도 될까 ?? 왜냐하면, 무조건 ! 기존에 나왔던 사각형을 탐색할 수 밖에 없기 때문이다.

    

     위의 예시만 보더라도, 왜 기존에 나왔던 사각형인지 알 수 있을 것이다. 가장 왼쪽 열에서 사각형을 만들기 시작할 경우

     시작점으로 돌아오기 직전의 좌표는 시작점의 오른쪽 위 좌표가 될 수 밖에 없고, 이는 이미 만들어진 사각형임을

     의미하기 때문이다.

     지금까지 내용을 정리해보자.

     1. 모든 좌표에서 모든 방향으로 탐색을 하더라도 정답을 받는데는 무리가 없지만 시간이 오래걸린다.

     2. 이를 해결하기 위해서 탐색의 시작을 무조건 오른쪽 아래로만 하도록 설정해주었다.

     3. 모든 행, 모든 열에 대해서 탐색을 하는 것이 아닌, 모든 행, 1 ~ N - 2열까지만 탐색을 하도록 설정해 주었다.

 

2) 그렇다면 이제부터 진짜 탐색을 어떻게 해야 하는지 구체적인 풀이방법에 대해서 알아보자.

   가장 처음에 본인은 이 과정을 재귀를 통한 탐색 법으로 구현했다고 하였다.

   본인은 DFS함수에서 총 7개의 매개변수를 사용해 주었다.

   DFS(int x , int y , int dir , int Line , int Cnt , int Sx, int Sy)

   각 매개변수의 의미부터 알아보자.

   1. int x, int y

   - 현재 좌표를 저장해 주는 매개변수이다. (x, y)

   2. int dir

   - 현재 진행방향을 저장해 주는 매개변수이다. 이 변수가 왜 필요한지는 밑에 'Line' 매개변수를 보면서 알아보자.

   3. int Line

   - 선분의 갯수를 저장하는 매개변수이다. 제대로 된 사각형이라면 선분의 갯수가 4개일 것이다. 그 이상이거나 그 이하라면

     제대로 된 사각형이 아닐 것이고 문제에서 원하는 답을 도출할 수 없을 것이다.

     따라서 본인은 사각형인지 판단하기 위해서 선분의 갯수를 저장하는 변수를 사용해 주었다.

     그렇다면 아래와 같은 상황을 보자.

    

    (0, 1) 좌표에서 빨간 화살표를 따라서 탐색을 시작했다고 생각해보자. 지금까지의 선분 상태를 보면

    (0, 1)과 (1, 2)가 연결된 선분 1개가 존재하는 상태이다. 이 때, 파랑색 화살표를 따라서 간다면 선분의 갯수는 어떻게

    바뀌게 될까 ?? 그대로 1개이다. 단지 그 선분의 길이가 길어진 것이지 절대로 선분이 하나 더 추가된 것이 아니다.

    하지만, 초록색 화살표를 따라가게 되면 ? 2개의 선분이 된다. 왜냐하면 저 화살표를 그려보면 다음과 같기 때문이다.

  

    파랑색 화살표를 따라 갈 경우 위와 같이 1개의 선분이 되지만, 초록색 화살표를 따라갈 경우 선분이 2개가 된다는

    것을 알 수 있다.

    즉, 선분의 갯수는 현재 진행방향에 영향을 미친다. 현재 진행방향과 탐색하려는 방향이 일치한다면 선분의 갯수는 그대로,

    그게 아니라면 선분의 갯수는 + 가 되게 된다. 이 부분 때문에 진행방향을 관리하는 변수 또한 넣어주었다.

    4. int Cnt

    - 디저트의 갯수를 Count해주는 변수이다.

    5. int Sx, int Sy

    - 시작 좌표를 저장하는 변수이다. 일반적인 DFS 탐색과 달리, 이미 방문한 좌표라고 해서 그냥 지나쳐 버리면 안된다.

      왜냐하면, 우리는 결국 시작점으로 돌아와야 하기 때문이다. 시작점은 이미 방문처리가 되있음에도 다시 돌아올 수

      있도록 만들어 주어야 한다. 즉, 이런 부분 때문에 시작점을 넣어주었다.

3) 그럼 지금부터는 위에서 설명한 부분을 코드로 잠시 확인해 보고, DFS내부는 어떻게 구현되어 있는지 확인해보자.

   먼저 DFS함수를 호출하는 부분이다.

void Solution()
{
    for (int i = 0; i < N; i++)                // 0행부터 N - 1행까지 탐색
    {
        for (int j = 1; j < N - 1; j++)        // 1열부터 N - 2열 까지만 탐색
        {
            Visit[i][j] = true;             // 시작점 = (i, j). 방문 표시
            NumVisit[MAP[i][j]] = true;   // 시작점의 디저트 방문 표시
            // 본인 코드 기준으로, dx[3], dy[3]은 우측 하단을 의미
            int nx = i + dx[3];             // 탐색을 우측하단으로 시작
            int ny = j + dy[3];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (NumVisit[MAP[nx][ny]] == false)
                {
                    NumVisit[MAP[nx][ny]] = true;
                    Visit[nx][ny] = true;
                    DFS(nx, ny, 3, 1, 2, i, j);    // 매개변수가 이렇게 설정되어 있는 이유는 밑에서 설명.
                    Visit[nx][ny] = false;
                    NumVisit[MAP[nx][ny]] = false;
                }
            }

            Visit[i][j] = false;
            NumVisit[MAP[i][j]] = false;
        }
    }
}  

   위의 부분은 DFS를 호출하는 부분이다.

   여기서, DFS함수가 DFS(nx, ny, 3, 1, 2, i, j) 로 호출된 이유를 알아보자.

   1. nx, ny

   - 우측하단에서 탐색을 시작하기 때문에 현재 좌표는 시작점의 우측하단 좌표인 (nx, ny)가 된다.

   2. Dir = 3

   - 본인 코드 기준, 우측 하단은 '3'으로 계산해 준다. 즉, 현재 진행방향은 '3'이 된다.

   3. Line = 1

   - 이미, 시작좌표와 우측하단의 좌표를 연결한 1개의 선분이 존재한 상태로 탐색을 시작한다.

     즉, 호출 할 때의 선분의 갯수는 1개이다.

   4. Cnt = 2

   - 현재까지 먹은 디저트는 시작좌표의 디저트 1개 + 시작좌표의 우측하단의 디저트 1개 = 총 2개이다.

   5. i, j

   - 시작점은 (i, j)이다. (nx, ny)가 아니다 !

     그렇다면 이제 DFS함수 내부를 확인해보자.

void DFS(int x, int y, int dir, int Line, int Cnt, int Sx, int Sy)
{
    if (Line > 4) return;            // 선분의 갯수가 4개 보다 더 크면, 이미 사각형이 아님을 의미.
    for (int i = 0; i < 4; i++)         // 모든 방향 탐색
    {
        int nx = x + dx[i];    
        int ny = y + dy[i];

        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (Visit[nx][ny] == true)            // 이미 방문한 좌표라면
            {                                  // 그냥 넘어가면 안된다 !
                if (Line >= 3 && Cnt >= 4)        // 이 부분 조건문은 아래에서 설명.
                {
                    if (nx == Sx && ny == Sy)    // 시작점이라면
                    {
                        Answer = Bigger(Answer, Cnt);    // 먹은 디저트의 갯수 갱신
                        return;
                    }
                }
            }
            else                        // 아직 방문하지 않은 좌표라면
            {
                if (NumVisit[MAP[nx][ny]] == false)    // 디저트 방문 여부 판단 후
                {
                    Visit[nx][ny] = true;
                    NumVisit[MAP[nx][ny]] = true;

                    if (dir == i) DFS(nx, ny, i, Line, Cnt + 1, Sx, Sy);

 // 기존의 탐색방향과 현재 탐색방향이 같으면 Line의 갯수는 그대로 DFS호출

                    else DFS(nx, ny, i, Line + 1, Cnt + 1, Sx, Sy);
                   // 그게 아니라면, Line의 갯수는 + 1 한 상태로 DFS호출
                    Visit[nx][ny] = false;
                    NumVisit[MAP[nx][ny]] = false;
                }
            }
        }
    }
}   

     DFS함수 내부 구현이다. 여기서, 이미 방문한 좌표를 만났을 때 걸려있는 조건문인

     if(Line >= 3 && Cnt >= 4) 에 대해서 알아보자.

     먼저, 제대로 된 사각형을 그렸다면, 최소 디저트의 갯수가 4개일 것이다. 즉, Cnt변수는 Cnt>=4 여야만 제대로 사각형을

     그렸다는 것을 의미한다.

     그렇다면 Line >= 3 이 부분을 생각해보자. 분명히 사각형은 선분의 갯수가 4개여야 하는데, 왜 3개일때도 조건문을

     걸어준 것일까?

     아래와 같은 2가지 상황을 생각해보자.

     시작점은 2개의 그림 모두 빨간점이고, 탐색 순서는 왼쪽 그림은

     A → B → C → D → A , 오른쪽 그림은 A → B → C → D → E → F → A 이다.

     그럼 먼저, 오른쪽 그림에서 'F'점일 때 'Line'변수의 값이 얼마일지 생각해보자.

     가장 먼저, 'B'에서 DFS가 호출되었을 것이므로 B에서 Line = 1.

     B → C로 갈 때, 진행방향이 바뀌었으므로 Line = 2

     C → D로 갈 때, 진행방향이 그대로 이므로 Line = 2

     D → E로 갈 때, 진행방향이 바뀌었으므로 Line = 3

     E → F로 갈 때, 진행바향이 바뀌었으므로 Line = 4

     F → A로 갈 때, 진행방향이 그대로이므로 Line = 4.

     즉, Line = 4일 것이다. 위에서도 말했지만, 정상적인 사각형이라면 Line의 갯수는 4개여야 맞다. 

     그렇다면, 왼쪽 그림을 한번 봐보도록 하자. 왼쪽 그림에서 'D'일 때 Line의 값은 얼마일까 ?

     'B'에서 DFS가 호출되었을 것이므로 B에서 Line = 1

     B → C로 갈 때, 진행 방향이 바뀌었으므로 Line = 2

     C → D로 갈 때, 진행 방향이 바뀌었으므로 Line = 3

     이 상태에서 D가 호출된 것이다.

     그럼, D에서는 4방향 중, 'A'와 'C' 둘 중 한곳으로 갈 수 있다. 하지만 'C'는 방문한 좌표이고, 시작점이 아니기

     때문에 갈 수 없다. 즉, 갈 수 있는 좌표는 'A' 뿐이다.

     'A'는 이미 방문한 좌표이지만 시작좌표이기 때문에 방문할 수 있는 것이다.

     그럼, 'A'좌표를 방문할 것이다. 그리고 디저트의 갯수를 갱신해줄 것이다. 근데 ! 문제는 현재 Line의 값은 '3' 이라는

     것이다. 즉, 방향이 바뀌고 바로 시작점에 도달할 경우, Line변수가 3으로 설정되어 있음에도 정상적인 사각형으로

     판단해줘야 한다는 것이다. 코드를 하나하나 따라가보면 Line 이 3인 이유를 알 수 있을 것이다.

     이러한 부분 때문에 if(Line == 4)가 아닌, if(Line >= 3)으로 설정해주었다. 선분이 3개만 만들었다고 판단했음에도

     사각형이 만들어지는 위와 같은 경우가 존재하기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool NumVisit[101];
 
int dx[] = { -1, -1, 1, 1 };
int dy[] = { -1, 1, -1, 1 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = -1;
    memset(Visit, false, sizeof(Visit));
    memset(NumVisit, false, sizeof(NumVisit));
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void DFS(int x, int y, int dir, int Line, int Cnt, int Sx, int Sy)
{
    if (Line > 4) return;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (Visit[nx][ny] == true)
            {
                if (Line >= 3 && Cnt >= 4)
                {
                    if (nx == Sx && ny == Sy)
                    {
                        Answer = Bigger(Answer, Cnt);
                        return;
                    }
                }
            }
            else
            {
                if (NumVisit[MAP[nx][ny]] == false)
                {
                    Visit[nx][ny] = true;
                    NumVisit[MAP[nx][ny]] = true;
 
                    if (dir == i) DFS(nx, ny, i, Line, Cnt + 1, Sx, Sy);
                    else DFS(nx, ny, i, Line + 1, Cnt + 1, Sx, Sy);
 
                    Visit[nx][ny] = false;
                    NumVisit[MAP[nx][ny]] = false;
                }
            }
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < N - 1; j++)
        {
            Visit[i][j] = true;
            NumVisit[MAP[i][j]] = true;
            
            int nx = i + dx[3]; 
            int ny = j + dy[3];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (NumVisit[MAP[nx][ny]] == false)
                {
                    NumVisit[MAP[nx][ny]] = true;
                    Visit[nx][ny] = true;
                    DFS(nx, ny, 3, 1, 2, i, j);
                    Visit[nx][ny] = false;
                    NumVisit[MAP[nx][ny]] = false;
                }
            }
 
            Visit[i][j] = false;
            NumVisit[MAP[i][j]] = false;
        }
    }
}
 
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;
}