(C++) 2105. [모의 SW 역량테스트] 디저트 카페

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AV5VwAr6APYDFAWu

예전에도 풀기는 했는데.. 예전에는 생길 수 있는 경로 유형을 다 list로 저장해서 처리했다면, 이번에는 정석으로 DFS로 풀었음.
– 네 모서리 점은 대각선으로 한 바퀴 돌아올 수 없으므로 제외
– 나머지 점은 LD (왼쪽 아래 대각선), RD (오른쪽 아래 대각선), RU (오른쪽 위 대각선), LU (왼쪽 위 대각선) 네 가지 중 가능한 경우에 한해 process_ 함수 호출됨
– 이 경우 한 바퀴를 잘 돌아오는지 확인하기 위해 LDAvail, RDAvail, RUAvail, LUAvail 변수를 함수에 담고 있다. 각각 해당 방향으로 전환한 적이 있는지 체크 (있으면 1, 없으면 0)한다. 처음에 process()에서 호출할 때 처음 정한 방향은 0, 나머지는 1로 호출됨.
– LDRUCnt는 / 대각선 (왼쪽 아래, 오른쪽 위), LURDCnt는 \ 대각선 (왼쪽 위, 오른쪽 아래) 방향으로 이동한 횟수를 기록. (아래 방향은 +1, 윗 방향은 -1)
이 변수들은 처음에 이동한만큼만 나중에 돌아올 수 있도록 처리하기 위함. LD/RU 혹은 LU/RD 중 나중에 선택된 방향의 경우 해당 변수가 0이 되면 무조건 방향 전환을 시킴.
– 기본적으로 호출될 때 해당 좌표의 디저트는 먹는 것으로 처리하고, 이후 다음 좌표 (해당 좌표+주어진 방향으로 계산) 를 기준으로 이동할 수 있는 방향들을 다 계산해서 함수를 recursive로 호출. 방향이 이상하게 이동하는 것을 막기 위해, 위에서 말한 [LD/RD/RU/LU]Avail 변수들이 사용됨. (한 번 간 방향으로 또 가지 못하게 하기 위해서)

#include <iostream>

using namespace std;

int map[20][20] = {{0}};
int containsNumber[100 + 1] = {0};

int maxDessert = 0;

void process(int size);
void process_(int numTry, int row, int column, int direction, int LDAvail, int RDAvail, int RUAvail, int LUAvail, int LDRUCnt, int LURDCnt, int size);

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int T = 0;
    cin >> T;

    for (int test_case = 1; test_case <= T; test_case++) {
        cout << "#" << test_case << ' ';

        maxDessert = -1;

        int numN = 0;
        cin >> numN; // map size

        // map construction
        for (int r = 0; r < numN; r++)
            for (int c = 0; c < numN; c++) 
                cin >> map[r];

        process(numN);
        if (maxDessert > 0)
            cout << maxDessert << '\n';
        else
            cout << -1 << '\n';
    }
}

void process(int size) {
    for (int r = 0; r < size; r++) {
        for (int c = 0; c < size; c++) {
            // 4 corner points cannot be the start point
            if ((r == 0 &amp;&amp; c == 0) || (r == 0 &amp;&amp; c == size - 1) || (r == size - 1 &amp;&amp; c == 0) || (r == size - 1 &amp;&amp; c == size - 1))
                continue;

            // LD (left-down) <v
            if (r != size - 1 &amp;&amp; c != 0)
                process_(1, r, c, 0, 0, 1, 1, 1, 0, 0, size);

            // RD (right-down) v>
            if (r != size - 1 &amp;&amp; c != size - 1)
                process_(1, r, c, 1, 1, 0, 1, 1, 0, 0, size);

            // RU (right-up) ^>
            if (r != 0 &amp;&amp; c != size - 1)
                process_(1, r, c, 2, 1, 1, 0, 1, 0, 0, size);

            // LU (left-up) <^
            if (r != 0 &amp;&amp; c != 0)
                process_(1, r, c, 3, 1, 1, 1, 0, 0, 0, size);
        }
    }
}

// direction (LD: 0, RD: 1, RU: 2, LU: 3)
void process_(int numTry, int row, int column, int direction, int LDAvail, int RDAvail, int RUAvail, int LUAvail, int LDRUCnt, int LURDCnt, int size) {
    int thisDessert = map[row][column];

    if (containsNumber[thisDessert] == 0) { // can eat this dessert
        containsNumber[thisDessert] = 1;

        int nextRow = row;
        int nextColumn = column;

        int LDRUCnt_ = LDRUCnt;
        int LURDCnt_ = LURDCnt;

        // move to next location
        switch (direction) {
            case 0: // LD
                nextRow++;
                nextColumn--;
                LDRUCnt_++;
            break;
            case 1: // RD
                nextRow++;
                nextColumn++;
                LURDCnt_++;
            break;
            case 2: // RU
                nextRow--;
                nextColumn++;
                LDRUCnt_--;
            break;
            case 3: // LU
                nextRow--;
                nextColumn--;
                LURDCnt_--;
            break;
        }

        // came back to initial position
        if (LDRUCnt_ == 0 &amp;&amp; LURDCnt_ == 0) {
            if (maxDessert < numTry)
                maxDessert = numTry;
        }
        else {
            // check if it can go further with other direction
            switch (direction) {
                case 0: // LD
                    // keep LD
                    if (nextRow < size - 1 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RUAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false) // if this is third/fourth direction, limit the number of movement to that of first/second direction
                            process_(numTry + 1, nextRow, nextColumn, 0, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LU
                    if (LUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RDAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, 0, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RD
                    if (RDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 1, LDAvail, 0, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);                
                    }
                    break;
                case 1: // RD
                    // keep RD
                    if (nextRow < size - 1 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 1, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LD
                    if (LDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RUAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 0, 0, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RU
                    if (RUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, 0, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
    
                    containsNumber[thisDessert] = 0; // restore
                    break;
                case 2: // RU
                    // keep RU
                    if (nextRow > 0 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LU
                    if (LUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RDAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, 0, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RD
                    if (RDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 1, LDAvail, 0, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }

                    break;
                case 3: // LU
                    // keep LU
                    if (nextRow > 0 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RDAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LD
                    if (LDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RUAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 0, 0, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RU
                    if (RUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, 0, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }

                    break;
            }
        }
        containsNumber[thisDessert] = 0; // restore
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.