(C++) 2112. [모의 SW 역량테스트] 보호 필름

Standard

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

분명 이전에 풀었던 문젠데, 시간 초과가 또 떠서 당황함.  분명 로직은 별로 차이 안 나는데….
– 처음에 통과 가능한지 확인해서 가능하면 바로 통과
– 통과 불가능하면, 맨 윗줄부터 한 줄씩 ‘A로 바꿈->테스트해서 통과하면 끝/아니면 다음 줄로 넘어감->B로 바꿈->테스트해서 통과하면 끝/아니면 다음 줄로 넘어감->아무것도 안 바꿈->테스트 해서 통과하면 끝/아니면 다음 줄로 넘어감’ 하도록 구현.
– 분명 로직은 잘못되지 않았는데 시간 초과가 떠서.. 고민 좀 하다가 ‘이미 구한 최소 약품 횟수를 넘어가는 경우가 나오면 바로 종료’하는 식으로 바운드를 만들었더니 통과. 1.2초였나..? (자바 때는 3.2초 정도 걸렸음… 응!?)

#include <iostream>

using namespace std;

int minModificationNum = 13 + 1;
int map[13][20] = {{0}}; // D (row), W (column) 

void process(int numD, int numW, int numK);
void process_(int depth, int numProcessed, int numD, int numW, int numK);
bool checkPass(int numD, int numW, int numK);

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

    //freopen("input.txt", "r", stdin);

    int T = 0;
    cin >> T;

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

        int numD = 0, numW = 8, numK = 3;
        cin >> numD >> numW >> numK; // K: threshold to pass

        minModificationNum = 13 + 1;

        // value 0: A, 1: B
        for (int r = 0; r < numD; r++) {
            for (int c = 0; c < numW; c++) {
                cin >> map[r];
            }
        }

        // check first it can be passed without modification
        bool passed = checkPass(numD, numW, numK);

        if (passed == true)
            cout << 0 << '\n';
        else {
            process(numD, numW, numK);
            cout << minModificationNum << '\n';
        }
    }
}

void process(int numD, int numW, int numK) {
    int backup[20] = {0};

    int theRow = 0;
    for (int i = 0; i < numW; i++)
        backup[i] = map[theRow][i];

    // first row changed to A
    for (int i = 0; i < numW; i++)
        map[theRow][i] = 0;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 1)
            minModificationNum = 1;

        for (int i = 0; i < numW; i++)
            map[theRow][i] = backup[i];

        return;
    }
    else 
        process_(theRow + 1, 1, numD, numW, numK);

    // first row changed to B
    for (int i = 0; i < numW; i++)
        map[theRow][i] = 1;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 1)
            minModificationNum = 1;

        for (int i = 0; i < numW; i++)
            map[theRow][i] = backup[i];

        return;
    }
    else 
        process_(theRow + 1, 1, numD, numW, numK);

    // first row not changed
    for (int i = 0; i < numW; i++)
        map[theRow][i] = backup[i];

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 0)
            minModificationNum = 0;
        return;
    }
    else 
        process_(theRow + 1, 0, numD, numW, numK);
}

void process_(int depth, int numProcessed, int numD, int numW, int numK) {
    if (depth == numD)
        return;
    if (numProcessed >= minModificationNum)
        return;

    int backup[20] = {0};

    for (int i = 0; i < numW; i++)
        backup[i] = map[depth][i];

    // first row changed to A
    for (int i = 0; i < numW; i++)
        map[depth][i] = 0;
    
    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed + 1)
            minModificationNum = numProcessed + 1;

        for (int i = 0; i < numW; i++)
            map[depth][i] = backup[i];

        return;
    }
    else
        process_(depth + 1, numProcessed + 1, numD, numW, numK);

    // first row changed to B
    for (int i = 0; i < numW; i++)
        map[depth][i] = 1;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed + 1)
            minModificationNum = numProcessed + 1;

        for (int i = 0; i < numW; i++)
            map[depth][i] = backup[i];

        return;
    }
    else
        process_(depth + 1, numProcessed + 1, numD, numW, numK);

    // first row not changed
    for (int i = 0; i < numW; i++)
        map[depth][i] = backup[i];

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed)
            minModificationNum = numProcessed;

        return;
    }
    else
        process_(depth + 1, numProcessed, numD, numW, numK);
}

bool checkPass(int numD, int numW, int numK) {
    bool passed = true;
    for (int c = 0; c < numW; c++) {
        int current = map[0];
        int count = 1;

        for (int r = 1; r < numD; r++) {
            if (current == map[r]) {
                count++;
                if (count == numK) // already passed
                    break;
            }
            else {
                current = map[r];
                count = 1;
            }
        }

        if (count < numK) {
            passed = false;
            break;
        }
    }

    return passed;
}

(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 && c == 0) || (r == 0 && c == size - 1) || (r == size - 1 && c == 0) || (r == size - 1 && c == size - 1))
                continue;

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

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

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

            // LU (left-up) <^
            if (r != 0 && 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 && 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 && nextColumn > 0) { // it can go
                        if ((RUAvail == 0 && 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 && nextRow > 0 && nextColumn > 0) { // it can go
                        if ((RDAvail == 0 && LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, 0, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RD
                    if (RDAvail == 1 && nextRow < size - 1 && nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 && 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 && nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 && LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 1, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LD
                    if (LDAvail == 1 && nextRow < size - 1 && nextColumn > 0) { // it can go
                        if ((RUAvail == 0 && LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 0, 0, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RU
                    if (RUAvail == 1 && nextRow > 0 && nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 && 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 && nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 && LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LU
                    if (LUAvail == 1 && nextRow > 0 && nextColumn > 0) { // it can go
                        if ((RDAvail == 0 && LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, 0, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RD
                    if (RDAvail == 1 && nextRow < size - 1 && nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 && 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 && nextColumn > 0) { // it can go
                        if ((RDAvail == 0 && LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LD
                    if (LDAvail == 1 && nextRow < size - 1 && nextColumn > 0) { // it can go
                        if ((RUAvail == 0 && LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 0, 0, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RU
                    if (RUAvail == 1 && nextRow > 0 && nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 && LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, 0, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }

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

(C++) 1953. [모의 SW 역량테스트] 탈주범 검거

Standard

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

문제 자체는 어렵지 않다. BFS 로 풀면 됨.
– 시작 위치 (맨홀 위치)부터 queue에 넣으면 됨. (시간 정보도 필요)
– queue에서 하나씩 dequeue하면서 좌우상하 위치로 도달 가능한지 (+방문한 적이 없는가) 체크하면서 도달 가능하면 visited mark하고 시간 1 추가해서 enqueue 
(dequeue할 때마다 도달가능한 곳 카운트 1씩 증가)
– 단, enqueue할 때 시간이 넘어간 경우 enqueue하지 않음
– queue에서 나온 후,   도달가능한 곳 카운트 해놓은 것 출력

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    //freopen("input.txt", "r", stdin);

    int T = 0;
    cin >> T;

    int map[50][50] = {0};
    int visited[50][50] = {0};
    int queueR[50*50] = {0};
    int queueC[50*50] = {0};
    int queueT[50*50] = {0};

    for (int test_case = 1; test_case <= T; test_case++) {
        int numN = 0, numM = 0, numR = 0, numC = 0, numL = 0;
        cin >> numN >> numM; // map size (row: N, column: M)
        cin >> numR >> numC; // loc of manhole (R, C)
        cin >> numL; // time elapsed after escape

        // add pipe information
        int numArrived = 0;
        for (int r = 0; r < numN; r++) 
            for (int c = 0; c < numM; c++) 
                cin >> map[r];

        for (int r = 0; r < numN; r++) 
            for (int c = 0; c < numM; c++) 
                visited[r] = 0;
        
        int queueFront = -1;
        int queueRear = -1;

        // first enqueue starting point
        if (queueFront == -1)
            queueFront = 0;

        queueRear++;
        queueR[queueRear] = numR;
        queueC[queueRear] = numC;
        queueT[queueRear] = 1;
        visited[numR][numC] = 1;

        // while the queue is not empty
        while (queueFront != -1 && queueFront <= queueRear) {
            // dequeue
            int myRow = queueR[queueFront];
            int myColumn = queueC[queueFront];
            int myTime = queueT[queueFront];
            queueFront++;

            //cout << myRow << '/' << myColumn << ' ' << myTime << '\n';
            numArrived++;

            // left, right, up, down
            int rowPair[4] = {0, 0, -1, 1};
            int columnPair[4] = {-1, 1, 0, 0};

            for (int i = 0; i < 4; i++) {
                int newRow = myRow + rowPair[i];
                int newColumn = myColumn + columnPair[i];

                // out of array, don't go further
                if (newRow < 0 || newRow > numN - 1 || newColumn < 0 || newColumn > numM - 1)
                    continue;

                // already visited, don't need to check more than once
                if (visited[newRow][newColumn] == 1)
                    continue;

                // can't go beyond time limit 
                if (myTime == numL)
                    continue;

                switch (i) {
                    case 0: // left
                        // current place: can go to left
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 3 || map[myRow][myColumn] == 6 || map[myRow][myColumn] == 7) {
                            // next place: can arrived from right
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 3 || map[newRow][newColumn] == 4 || map[newRow][newColumn] == 5) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 1: // right
                        // current place: can go to right
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 3 || map[myRow][myColumn] == 4 || map[myRow][myColumn] == 5) {
                            // next place: can arrived from left
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 3 || map[newRow][newColumn] == 6 || map[newRow][newColumn] == 7) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 2: // up
                        // current place: can go to up
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 2 || map[myRow][myColumn] == 4 || map[myRow][myColumn] == 7) {
                            // next place: can arrived from down
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 2 || map[newRow][newColumn] == 5 || map[newRow][newColumn] == 6) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 3: // down
                        // current place: can go to down
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 2 || map[myRow][myColumn] == 5 || map[myRow][myColumn] == 6) {
                            // next place: can arrived from up
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 2 || map[newRow][newColumn] == 4 || map[newRow][newColumn] == 7) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                }
            }
        }

        cout << '#' << test_case << ' ' << numArrived << '\n';
    }
}

(C++) 1949. [모의 SW 역량테스트] 등산로 조성

Standard

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

이미 푼 문제임에도 불구하고 처음에 아무 것도 안 떠올라서 당황했지만…
다 짜고 보니 더 효율적인 코드가 됨.
– 최대 높이인 곳들을 list에 삽입
– DFS로 짬. 각 함수에서 visited map을 만들고 처음 최대 높이인 곳을 visited로 처리. (이후 DFS 함수에서는 방문할 수 있는 경우만 실행되니 visited는 항상 1로 처리)
이후, 왼쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 오른쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 위쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 아래쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
(각 경우, 더 이상 진행이 안 되면 이후 진행이 불가능하므로, 현재까지의 거리를 업데이트함)

#include <iostream>
#include <cstdlib>

using namespace std;

void process (int row, int column, int **map, int size, int k);
void process_(int length, int row, int column, int** map, int** visited, int size, int k, bool constructed);

int maxLength = 1;

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    //freopen("input.txt", "r", stdin);
    int T = 0;
    cin >> T;

    int** map = (int**) malloc (8 * sizeof(int*));
    for (int i = 0; i < 8; i++) {
        map[i] = (int*) malloc (8 * sizeof(int));
    }

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

        maxLength = 0;

        int numN = 0, numK = 0;
        cin >> numN >> numK; // N: map size, k: construction depth limit

        int maxValue = 0, maxRow[5] = {0}, maxColumn[5] = {0}, maxIdx = -1;

        for (int r = 0; r < numN; r++) {
            for (int c = 0; c < numN; c++) {
                cin >> map[r];
                if (maxValue < map[r]) {
                    maxValue = map[r];
                    maxIdx = 0;
                    maxRow[maxIdx] = r;
                    maxColumn[maxIdx] = c;
                }
                else if (maxValue == map[r]) {
                    maxIdx++;
                    maxRow[maxIdx] = r;
                    maxColumn[maxIdx] = c;
                }
            }
        }

        for (int i = 0; i < maxIdx + 1; i++) {
            process(maxRow[i], maxColumn[i], map, numN, numK);
        }

        cout << maxLength << '\n';
    }
	
	return 0;
}

void process (int row, int column, int **map, int size, int k) {
    // visited map
    int **visited = (int**) malloc (size * sizeof(int*));
    for (int i = 0; i < size; i++) 
        visited[i] = (int*) malloc (size * sizeof(int));
    
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            visited[i][j] = 0;

    visited[row][column] = 1;        

    bool constructed = false;

    // left direction
    if (column > 0 && map[row][column] > map[row][column - 1]) 
        process_(2, row, column - 1, map, visited, size, k, constructed);
    else if (constructed == false && column > 0 && map[row][column] > map[row][column - 1] - k) {
        int backup = map[row][column - 1];
        map[row][column - 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row, column - 1, map, visited, size, k, true);
        map[row][column - 1] = backup;
    }

    // right direction
    if (column < size - 1 && map[row][column] > map[row][column + 1])
        process_(2, row, column + 1, map, visited, size, k, constructed);
    else if (constructed == false && column < size - 1 && map[row][column] > map[row][column + 1] - k) {
        int backup = map[row][column + 1];
        map[row][column + 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row, column + 1, map, visited, size, k, true);
        map[row][column + 1] = backup;
    }

    // up direction
    if (row > 0 && map[row][column] > map[row - 1][column])
        process_(2, row - 1, column, map, visited, size, k, constructed);
    else if (constructed == false && row > 0 && map[row][column] > map[row - 1][column] - k) {
        int backup = map[row - 1][column];
        map[row - 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row - 1, column, map, visited, size, k, true);
        map[row - 1][column] = backup;
    }

    // down direction
    if (row < size - 1 && map[row][column] > map[row + 1][column])
        process_(2, row + 1, column, map, visited, size, k, constructed);
    else if (constructed == false && row < size - 1 && map[row][column] > map[row + 1][column] - k) {
        int backup = map[row + 1][column];
        map[row + 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row + 1, column, map, visited, size, k, true);
        map[row + 1][column] = backup;
    }
}

void process_(int length, int row, int column, int** map, int** visited, int size, int k, bool constructed) {
    int **newVisited = (int**) malloc (size * sizeof(int*));
    for (int i = 0; i < size; i++) 
        newVisited[i] = (int*) malloc (size * sizeof(int));
    
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            newVisited[i][j] = visited[i][j];

    newVisited[row][column] = 1;
    
    if (column > 0 && newVisited[row][column - 1] == 0 && map[row][column] > map[row][column - 1])
        process_(length + 1, row, column - 1, map, newVisited, size, k, constructed);
    else if (constructed == false && column > 0 && newVisited[row][column - 1] == 0 && map[row][column] > map[row][column - 1] - k) {
        int backup = map[row][column - 1];
        map[row][column - 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row, column - 1, map, newVisited, size, k, true);
        map[row][column - 1] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (column < size - 1 && newVisited[row][column + 1] == 0 && map[row][column] > map[row][column + 1])
        process_(length + 1, row, column + 1, map, newVisited, size, k, constructed);
    else if (constructed == false && column < size - 1 && newVisited[row][column + 1] == 0 && map[row][column] > map[row][column + 1] - k) {
        int backup = map[row][column + 1];
        map[row][column + 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row, column + 1, map, newVisited, size, k, true);
        map[row][column + 1] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (row > 0 && newVisited[row - 1][column] == 0 && map[row][column] > map[row - 1][column])
        process_(length + 1, row - 1, column, map, newVisited, size, k, constructed);
    else if (constructed == false && row > 0 && newVisited[row - 1][column] == 0 && map[row][column] > map[row - 1][column] - k) {
        int backup = map[row - 1][column];
        map[row - 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row - 1, column, map, newVisited, size, k, true);
        map[row - 1][column] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (row < size - 1 && newVisited[row + 1][column] == 0 && map[row][column] > map[row + 1][column])
        process_(length + 1, row + 1, column, map, newVisited, size, k, constructed);
    else if (constructed == false && row < size - 1 && newVisited[row + 1][column] == 0 && map[row][column] > map[row + 1][column] - k) {
        int backup = map[row + 1][column];
        map[row + 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row + 1, column, map, newVisited, size, k, true);
        map[row + 1][column] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }
}

(C++) 1767. [SW Test 샘플문제] 프로세서 연결하기

Standard

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

예전에 풀어봤던 문제인데, 다른 이유로 (!?) 헤맨 문제.
– 벽에 붙어있는 CPU는 map에만 넣고, 벽에 붙어 있지 않은 CPU는 queue에 목록으로 넣음
– 처음에는 로직을 이상하게 (?) 짜서 DFS 함수를 CPU 별로 한 방향씩 탐색하도록 시키고, 해당 함수에서 CPU가 포함 불가할 때 4가지 방향, 포함 가능할 때 4가지 방향 이런 식으로 뻗어가다 보니….. O(8^n)이 되어버린 이유로 시간 초과가 나옴
– 예전에 했던 코드를 다시 보니 DFS 함수에는 CPU 정보만 넣고, 내부에서 각 방향으로 선 설치가 가능한 경우+설치 안하는 경우 해서 O(5^n)의 알고리즘을 만드니 시간 통과.

– 효율성의 극대화를 위해 매번 DFS 호출할 때마다 전체 맵 복사 대신 해당하는 부분 (CPU 전선이 설치되는 방향)만 백업해서 처리함.
— 좌로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트 
— 우로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트
— 위로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트
— 아래로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트
— 추가하지 않고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트

#include <iostream>
#include <cstdlib>

using namespace std;

int maxNumCPU = 0, minNumLine = 0;
int CPUListRow[12]; // CPUListRow[12]
int CPUListColumn[12]; // CPUListColumn[12]
int CPUIdx = -1;
int numN = 0;

void process (int** map);
void process_ (int numTry, int lineLength, int succeedCPU, int** map);

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

    int** map;
    map = (int**) malloc (12 * sizeof(int*));
    for (int i = 0; i < 12; i++)
        map[i] = (int*)  malloc (12 * sizeof(int));

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

        cin >> numN;

        maxNumCPU = 0;
        minNumLine = 0;
        CPUIdx = -1;

        for (int r = 0; r < numN; r++) {
            for (int c = 0; c < numN; c++) {
                cin >> map[r];
                // ignore CPUs at edge. They are placed in the map, but don't need to be connected by line
                if (r != 0 && r != numN -1 && c != 0 && c != numN - 1 && map[r] == 1) {
                    CPUIdx++;
                    CPUListRow[CPUIdx] = r;
                    CPUListColumn[CPUIdx] = c;
                }
            }
        }

        process(map);

        cout << minNumLine << '\n';
    }
	
	return 0;
}

void process (int** map) {
    process_(1, 0, 0, map);
}

void process_ (int numTry, int lineLength, int succeedCPU, int** map) {
    int myRow = CPUListRow[numTry - 1];
    int myColumn = CPUListColumn[numTry - 1];

    int backupContent[12] = {0};

    // 1. check left
    int failed = false;
    int thisLineLength = 0;

    // backup
    for (int c = 0; c < numN; c++) 
        backupContent = map[myRow];
    
    for (int c = myColumn - 1; c >= 0; c--) {
        if (map[myRow] == 0) {
            map[myRow] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    } 
    // restore
    for (int c = 0; c < numN; c++) 
        map[myRow] = backupContent;

    // 2. check right
    failed = false;
    thisLineLength = 0;

    // backup
    for (int c = 0; c < numN; c++) 
        backupContent = map[myRow];
    
    for (int c = myColumn + 1; c < numN; c++) {
        if (map[myRow] == 0) {
            map[myRow] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    }

    // restore
    for (int c = 0; c < numN; c++) 
        map[myRow] = backupContent;

    // 3. check up
    failed = false;
    thisLineLength = 0;

    // backup
    for (int r = 0; r < numN; r++)
        backupContent[r] = map[r][myColumn];

    for (int r = myRow - 1; r >= 0; r--) {
        if (map[r][myColumn] == 0) {
            map[r][myColumn] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    }

    // restore
    for (int r = 0; r < numN; r++)
        map[r][myColumn] = backupContent[r];

    // 4. check down
    failed = false;
    thisLineLength = 0;

    // backup
    for (int r = 0; r < numN; r++)
        backupContent[r] = map[r][myColumn];

    for (int r = myRow + 1; r < numN; r++) {
        if (map[r][myColumn] == 0) {
            map[r][myColumn] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    } 
    
    // restore
    for (int r = 0; r < numN; r++)
        map[r][myColumn] = backupContent[r];

    // 5. go without added
    if (numTry < CPUIdx + 1)
        process_(numTry + 1, lineLength, succeedCPU, map);
    else {
        if (maxNumCPU < succeedCPU) {
            maxNumCPU = succeedCPU;
            minNumLine = lineLength;
        }
        else if (maxNumCPU == succeedCPU) {
            if (minNumLine > lineLength)
                minNumLine = lineLength;
        }
    }
}

(C++) 13458번: 시험 감독

Standard

문제 링크: https://www.acmicpc.net/problem/13458

-총감독과 부감독이 있음. 총감독은 시험장 별로 1명만, 부감독은 여러명이 있어도 됨.
– 시험장 별로 응시자-총감독의 감독인원(B)을 해서 0 이하이면 감독관은 1명 필요함.
– 0 초과면 이후 부감독 감독인원 (C)로 나눔. 이 나눈 값에 나머지가 있는 경우 1을 더하면 필요한 부감독관 수가 됨.
– 최종값은 1 + 위에서 나눈 값 + 나머지가 있는 경우 1.

#include <iostream>

using namespace std;

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

    // num of test sites
    int numN = 0;
    cin >> numN;

    // num of applicants for each test site
    int numApplicants[numN];
    for (int i = 0; i < numN; i++) 
        cin >> numApplicants[i];
    
    // capacity of proctor, vice proctor
    int numB = 0, numC = 0; 
    cin >> numB;
    cin >> numC;

    long long count = 0;
    for (int i = 0; i < numN; i++) {
        int local_count = 0;

        int tmp = numApplicants[i];
        
        // only proctor required
        tmp -= numB;
        if (tmp <= 0) {
            count++;
            continue;
        }

        local_count++; // one proctor
        
        // vice proctor required
        local_count += tmp / numC;
        if (tmp % numC != 0)
            local_count++;
        
        count += local_count;
    }

    cout << count;
}

(C++) 3190번: 뱀

Standard

문제 링크: https://www.acmicpc.net/problem/3190

– 지도에서 0: 빈 곳, 1: 사과, 2: 몸 (머리 포함)으로 저장.
– 뱀의 몸 정보를 queue에 추가. (맨 뒤가 머리가 가도록 정보가 업데이트됨)
– 0부터 시작해서 주어진 방향으로 이동할 좌표 (nextHeadX, nextHeadY) 계산한 후, 벽돌에 부딪히는 경우나 이미 몸이 있는 경우 정지. 
– 이동할 곳에 사과가 있는 경우, 해당 장소를 map에서 2로 갱신하고 head 정보 업데이트. 몸 정보 업데이트.
– 이동할 곳에 사과가 없는 경우, 해당 장소를 2로 갱신, head 정보 갱신, 몸 정보 업데이트 (단 다른 점은 tail index (queue에서는 front)를 1 증가시킴))
– 이후 정해진 정보에 따라 방향 전환을 수행.

#include <iostream>

using namespace std;

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

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

    int map[numN][numN]; // 0: empty, 1: apple, 2: body
    for (int i = 0; i < numN; i++)
        for (int j = 0; j < numN; j++)
            map[i][j] = 0;

    // num of apple(s)
    int numK = 0;
    cin >> numK;

    for (int i = 0; i < numK; i++) {
        int tmpY = 0, tmpX = 0;
        cin >> tmpY;
        cin >> tmpX;

        map[tmpX - 1][tmpY - 1] = 1; // 1: apple
    }

    // num of direction change
    int numL = 0;
    cin >> numL;

    int changeAt[numL];
    char changeTo[numL];
    int currIdx = 0;

    for (int i = 0; i < numL; i++) {
        cin >> changeAt[i];
        cin >> changeTo[i];
    }   

    // current time, starting from 0
    int second = 0;
    int direction = 90; // up: 0, right: 90, down: 180, left: 270

    int snakeXList[numN * numN];
    int snakeYList[numN * numN];
    int headIdx = 0;
    int tailIdx = 0;

    snakeXList[headIdx] = 0;
    snakeYList[headIdx] = 0;

    map[snakeXList[headIdx]][snakeYList[headIdx]] = 2; // body

    while(true) {
        second++;

        int nextHeadX = 0;
        int nextHeadY = 0;

        switch (direction) {
            case 0:
                nextHeadX = snakeXList[headIdx];
                nextHeadY = snakeYList[headIdx] - 1;
                break;
            case 90:
                nextHeadX = snakeXList[headIdx] + 1;
                nextHeadY = snakeYList[headIdx];
                break;
            case 180:
                nextHeadX = snakeXList[headIdx];
                nextHeadY = snakeYList[headIdx] + 1;
                break;
            case 270:
                nextHeadX = snakeXList[headIdx] - 1;
                nextHeadY = snakeYList[headIdx];
                break;
        }

        // it it touches wall, finish
        if (nextHeadX == -1 || nextHeadX == numN || nextHeadY == -1 || nextHeadY == numN) {
            break;
        }

        // check next location
        if (map[nextHeadX][nextHeadY] == 2) {
            break;
        }
        else if (map[nextHeadX][nextHeadY] == 1) { // eat apple
            // just extend 
            headIdx++;
            snakeXList[headIdx] = nextHeadX;
            snakeYList[headIdx] = nextHeadY;

            map[snakeXList[headIdx]][snakeYList[headIdx]] = 2;
        }
        else { // no apple, just move
            map[snakeXList[tailIdx]][snakeYList[tailIdx]] = 0;
            tailIdx++; // increase tall index (to simplify process movement)

            headIdx++;
            snakeXList[headIdx] = nextHeadX;
            snakeYList[headIdx] = nextHeadY;

            map[snakeXList[headIdx]][snakeYList[headIdx]] = 2;
        }

        // has move information
        if (numL >= currIdx) {
            if (changeAt[currIdx] == second) {
                if (changeTo[currIdx] == 'L') {
                    direction -= 90;
                    if (direction < 0)
                        direction += 360;
                }
                else if (changeTo[currIdx] == 'D') {
                    direction += 90;
                    direction %= 360;
                }

                currIdx++;
            }
        }
    }

    cout << second;
}

(C++) 12100번: 2048 (Easy)

Standard

문제 링크: https://www.acmicpc.net/problem/12100

유명한 게임이라 게임 로직 자체는 설명할 필요가 없을 듯.
– [좌/우/상/하]^5 번 움직이는 경우의 수가 있으므로 DFS로 처리.
– 각 블록 별로 merged 맵이 있음. 이 맵은 한 번 이동할 때 merged되지 않은 같은 숫자의 두 블록만 합쳐지고, 다른 경우는 합쳐지지 않게 하는 역할.
– 각 블록이 원하는 방향으로 빈 공간이 있을 때까지 이동. 각 블럭이 빈 공간이 없을 때까지 이동 후, 자기 앞에 있는 블록과 합쳐질 조건이 되는 경우 (둘 다 같은 숫자, 둘 다 merge된 적이 없음) 합쳐지고, 합쳐진 블럭은 merged=1로 설정됨.
– 각 경우 5번 다 움직이고 나서 숫자가 가장 블록을 기록함.

#include <iostream>
#include <cstdlib>

using namespace std;
const int limit = 5;

int numN = 0;
int maxBlock = 0;

void process(int** map);
void process_(int tryNum, char direction, int** map);

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

    cin >> numN;

    int **map = NULL; // int map[numN][numN]
    map = (int**) malloc (numN * sizeof(int*));
    for (int i = 0; i < numN; i++)
        map[i] = (int*) malloc (numN * sizeof(int));

    for (int i = 0; i < numN; i++) {
        for (int j = 0; j < numN; j++) {
            cin >> map[j][i];
        }
    }

    // It's DFS!
    process(map);

    cout << maxBlock;
}

void process(int** map) {
    process_(1, 'U', map); // to Up
    process_(1, 'D', map); // to Down
    process_(1, 'L', map); // to Left
    process_(1, 'R', map); // to Right
}

void process_(int tryNum, char direction, int** map) {
    int** newMap;
    newMap = (int**) malloc (numN * sizeof(int*));
    for (int i = 0; i < numN; i++)
        newMap[i] = (int*) malloc (numN * sizeof(int));

    for (int i = 0; i < numN; i++) {
        for (int j = 0; j < numN; j++) {
            newMap[j][i] = map[j][i];;
        }
    }

    // always initialize
    int **merged = NULL; // int merged[numN][numN]
    merged = (int**) malloc (numN * sizeof(int*));
    for (int i = 0; i < numN; i++)
        merged[i] = (int*) malloc (numN * sizeof(int));

    for (int i = 0; i < numN; i++) 
        for (int j = 0; j < numN; j++) 
            merged[j][i] = 0;

    switch (direction) {
        case 'U':
            for (int i = 1; i < numN; i++) { // from second row
                for (int j = 0; j < numN; j++) { // from first column
                    for (int k = i; k > 0; k--) { // move upward as much as possible
                        if (newMap[j][k] != 0) {
                            if (newMap[j][k - 1] == 0) { // can move
                                newMap[j][k - 1] = newMap[j][k];
                                merged[j][k - 1] = merged[j][k];
                                newMap[j][k] = 0;
                                merged[j][k] = 0;
                            }
                            else if (newMap[j][k - 1] == newMap[j][k] && merged[j][k - 1] == 0 && merged[j][k] == 0) { // can merge
                                newMap[j][k - 1] *= 2;
                                newMap[j][k] = 0;
                                merged[j][k - 1] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
        case 'D':
            for (int i = numN - 2; i >= 0; i--) { // from second last row
                for (int j = 0; j < numN; j++) { // from first column
                    for (int k = i; k < numN - 1; k++) { // move downward as much as possible
                        if (newMap[j][k] != 0) {
                            if (newMap[j][k + 1] == 0) { // can move
                                newMap[j][k + 1] = newMap[j][k];
                                merged[j][k + 1] = merged[j][k];
                                newMap[j][k] = 0;
                                merged[j][k] = 0;
                            }
                            else if (newMap[j][k + 1] == newMap[j][k] && merged[j][k + 1] == 0 && merged[j][k] == 0) { // can merge
                                newMap[j][k + 1] *= 2;
                                newMap[j][k] = 0;
                                merged[j][k + 1] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
        case 'L':
            for (int i = 1; i < numN; i++) { // from second column
                for (int j = 0; j < numN; j++) { // from first row
                    for (int k = i; k > 0; k--) { // move leftward as much as possible
                        if (newMap[k][j] != 0) {
                            if (newMap[k - 1][j] == 0) { // can move
                                newMap[k - 1][j] = newMap[k][j];
                                merged[k - 1][j] = merged[k][j];
                                newMap[k][j] = 0;
                                merged[k][j] = 0;
                            }
                            else if (newMap[k - 1][j] == newMap[k][j] && merged[k - 1][j] == 0 && merged[k][j] == 0) { // can merge
                                newMap[k - 1][j] *= 2;
                                newMap[k][j] = 0;
                                merged[k - 1][j] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
        case 'R':
            for (int i = numN - 2; i >= 0; i--) { // from second last column
                for (int j = 0; j < numN; j++) { // from first row
                    for (int k = i; k < numN -1; k++) { // move rightward as much as possible
                        if (newMap[k][j] != 0) {
                            if (newMap[k + 1][j] == 0) { // can move
                                newMap[k + 1][j] = newMap[k][j];
                                merged[k + 1][j] = merged[k][j];
                                newMap[k][j] = 0;
                                merged[k][j] = 0;
                            }
                            else if (newMap[k + 1][j] == newMap[k][j] && merged[k + 1][j] == 0 && merged[k][j] == 0) { // can merge
                                newMap[k + 1][j] *= 2;
                                newMap[k][j] = 0;
                                merged[k + 1][j] = 1;

                                break;
                            }
                        }
                    }
                }
            }
            break;
    }

    for (int i = 0; i < numN; i++)
        free(merged[i]);
    free(merged);

    if (tryNum == limit) {
        for (int i = 0; i < numN; i++) {
            for (int j = 0; j < numN; j++) {
                if (maxBlock < newMap[j][i])
                    maxBlock = newMap[j][i];
            }
        }
    }
    else { // proceed more
        process_(tryNum + 1, 'U', newMap); // to Up
        process_(tryNum + 1, 'D', newMap); // to Down
        process_(tryNum + 1, 'L', newMap); // to Left
        process_(tryNum + 1, 'R', newMap); // to Right
    }

    for (int i = 0; i < numN; i++)
        free(newMap[i]);
    free(newMap);

}

(C++) 13460번: 구슬 탈출 2

Standard

문제 링크: https://www.acmicpc.net/problem/13460

[좌/우/상/하]^10 번 움직여서 변화를 트래킹하면 됨. 그래서 DFS로 분류함. 
– 왼쪽/오른쪽/위/아래 로 움직일 때 누가 먼저 움직이는지 체크함. 왼쪽/오른쪽은 같은 가로줄에 있을 때, 위/아래는 같은 세로줄에 있을 때 확인 필요. 아닌 경우 상관 없음.
– 각 구슬 별로 지정된 방향으로 이동. 빈 공간이면 이동, 구멍이면 빠져나감 (구슬 좌표 -1, -1로), 벽이거나 다른 구슬이 있으면 움직이지 않음. 다 움직이고 나면 최종 구슬 좌표 업데이트.
– 두 구슬 다 업데이트가 되고 나면 우선 파란 구슬이 구멍으로 나갔는지 확인 (실패 여부 확인). 파란 구슬이 나가지 않았으면 다음 빨간 구슬이 구멍으로 나갔는지 확인 (성공 여부 확인). 두 구슬 다 밖이 아니면 다음 단계로 진행.
– 10번 움직이고 나서도 두 구슬이 밖으로 나가지 않았으면 실패로 처리.

– DFS 처리가 끝나고 나면 최소로 움직인 횟수 (실패면 -1) 출력.

#include <iostream>
#include <cstdlib>

using namespace std;

char** map = NULL; // char map[numN][numM]
int numTrial = 11;
int numN = 0, numM = 0;

void process(int redR, int redC, int blueR, int blueC);
void process_(int tryNum, char direction, int redR, int redC, int blueR, int blueC);

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

    cin >> numN; // row
    cin >> numM; // column
    
    map = (char**) malloc (numN * sizeof(char*));
    for (int i = 0; i < numN; i++) 
        map[i] = (char*) malloc (numM * sizeof(char));
    
    int redBallRow = 0, redBallColumn = 0;
    int blueBallRow = 0, blueBallColumn = 0;
    int exitRow = 0, exitColumn = 0;
    
    char* tmp = (char*) malloc ((numM + 1) * sizeof(char));
    for (int i = 0; i < numN; i++) {
        cin >> tmp;
        for (int j = 0; j < numM; j++) {
            map[i][j] = tmp[j];
            if (map[i][j] == 'B') {
                blueBallRow = i;
                blueBallColumn = j;
            }
            else if (map[i][j] == 'R') {
                redBallRow = i;
                redBallColumn = j;
            }
            else if (map[i][j] == 'O') {
                exitRow = i;
                exitColumn = j;
            }            
        }
    }

    process(redBallRow, redBallColumn, blueBallRow, blueBallColumn);
    if (numTrial != 11)
        cout << numTrial;
    else
        cout << -1;
}

void process(int redR, int redC, int blueR, int blueC) {
    process_(1, 'L', redR, redC, blueR, blueC);
    process_(1, 'R', redR, redC, blueR, blueC);
    process_(1, 'U', redR, redC, blueR, blueC);
    process_(1, 'D', redR, redC, blueR, blueC);
}

void process_(int tryNum, char direction, int redR, int redC, int blueR, int blueC) {
    int newRedR = redR, newRedC = redC;
    int newBlueR = blueR, newBlueC = blueC;

    char order[2] = {' ', ' '};

    // try to move
    // 1. who to start first?
    switch (direction) {
        case 'L':
            if (newRedR == newBlueR && newBlueC < newRedC) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
        case 'R':
            if (newRedR == newBlueR && newBlueC > newRedC) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
        case 'U':
            if (newRedC == newBlueC && newBlueR < newRedR) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
        case 'D':
            if (newRedC == newBlueC && newBlueR > newRedR) {
                order[0] = 'B';
                order[1] = 'R';
            }
            else {
                order[0] = 'R';
                order[1] = 'B';
            }
            break;
    }

    // 2. move
    for (int i = 0; i < 2; i++) { 
        int curR = 0, curC = 0;
        if (order[i] == 'R') {
            curR = newRedR;
            curC = newRedC;
        }
        else {
            curR = newBlueR;
            curC = newBlueC;
        }

        switch (direction) {
            case 'L':
                for (int j = curC - 1; j >= 0; j--) {
                    if (map[curR][j] == '.') 
                        curC = j;
                    else if (map[curR][j] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[curR][j] == '#') 
                        break;
                    else if (map[curR][j] == 'B') 
                        break;
                    else if (map[curR][j] == 'R') 
                        break;                    
                }
                break;
            case 'R':
                for (int j = curC + 1; j < numM; j++) {
                    if (map[curR][j] == '.') 
                        curC = j;
                    else if (map[curR][j] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[curR][j] == '#') 
                        break;
                    else if (map[curR][j] == 'B') 
                        break;
                    else if (map[curR][j] == 'R') 
                        break;       
                }
                break;
            case 'U':
                for (int j = curR - 1; j >= 0; j--) {
                    if (map[j][curC] == '.') 
                        curR = j;
                    else if (map[j][curC] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[j][curC] == '#') 
                        break;
                    else if (map[j][curC] == 'B') 
                        break;
                    else if (map[j][curC] == 'R') 
                        break;       
                }
                break;
            case 'D':
                for (int j = curR + 1; j < numN; j++) {
                    if (map[j][curC] == '.') 
                        curR = j;
                    else if (map[j][curC] == 'O') {
                        curR = -1;
                        curC = -1;
                        break;
                    }
                    else if (map[j][curC] == '#') 
                        break;
                    else if (map[j][curC] == 'B') 
                        break;
                    else if (map[j][curC] == 'R') 
                        break;       
                }
                break;
        }

        if (order[i] == 'R') {
            newRedR = curR;
            newRedC = curC;

            map[redR][redC] = '.';
            if (newRedR != -1 && newRedC != -1)
                map[newRedR][newRedC] = 'R';
        }
        else {
            newBlueR = curR;
            newBlueC = curC;

            map[blueR][blueC] = '.';
            if (newBlueR != -1 && newBlueC != -1)
                map[newBlueR][newBlueC] = 'B';
        }
    }

    if (newBlueR == -1 && newBlueC == -1) { // fail
        // don't proceed, just restore
        map[blueR][blueC] = 'B';
        map[redR][redC] = 'R';
        if (newRedR != -1 && newRedC != -1)
            map[newRedR][newRedC] = '.';
    }
    else if (newRedR == -1 && newRedC == -1) { // success
        // update
        if (numTrial > tryNum)
            numTrial = tryNum;

        // restore
        map[blueR][blueC] = 'B';
        map[newBlueR][newBlueC] = '.';
        map[redR][redC] = 'R';
    }
    else { // proceed more
        if (tryNum == 10) { // can't proceed more
            // don't proceed, just restore
            map[blueR][blueC] = 'B';
            map[newBlueR][newBlueC] = '.';
            map[redR][redC] = 'R';
            map[newRedR][newRedC] = '.';
        }
        else {
            // proceed
            process_(tryNum + 1, 'L', newRedR, newRedC, newBlueR, newBlueC);
            process_(tryNum + 1, 'R', newRedR, newRedC, newBlueR, newBlueC);
            process_(tryNum + 1, 'U', newRedR, newRedC, newBlueR, newBlueC);
            process_(tryNum + 1, 'D', newRedR, newRedC, newBlueR, newBlueC);

            // restore
            map[blueR][blueC] = 'B';
            map[newBlueR][newBlueC] = '.';
            map[redR][redC] = 'R';
            map[newRedR][newRedC] = '.';
        }
    }
}

(C++) 5656. [모의 SW 역량테스트] 벽돌 깨기

Standard

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

로직은 Java와 같음.
– 가지의 수는  (numW)^numN 이다. 여기서 numW는 최대 12이고 N은 최대 4이므로 최대 20736개의 경우를 계산해 보면 됨. DFS를 쓰면 됨.
– 선택된 column에서 가장 위의 벽돌이 어딘지 우선 탐색. (만약 벽돌이 없으면 변화가 안 생기기 때문에 바로 다음 단계로 넘어감) 그리고 그 벽돌을 removeMap에 등록 (removeMap: 제거할 벽돌 목록)
– 그 벽돌을 시작으로 해서 같이 깨지는 벽돌을 모두 탐색함. 최초 벽돌에 1차 영향을 받는 벽돌들을 removeMap에 추가하고, 크기가 1보다 큰 벽돌은 queue에 추가함.
– 이후 queue가 빌 때까지 영향 받는 벽돌 탐색 및 queue 추가 (벽돌 숫자가 1보다 큰 경우)를 수행. 단, 한 번 removeMap에 추가된 벽돌은 다시 queue 추가하지 않음.
– removeMap 작성이 완료되면 이후 필요한 벽돌들을 모두 제거한 후, 밑으로 끌어당기는 작업 수행.
– 벽돌들이 모두 밑으로 내려오면 다음 단계로 넘어감. 단 최대 단계까지 이미 수행한 경우, 남은 벽돌 수를 세서 최소값인 경우만 저장.

#include <iostream>
#include <cstdlib>
//#include <cstdio>

using namespace std;

int numN = 0, numW = 0, numH = 0;
int minBlocks = 0;

void process(int** map);
void process_(int numTry, int theColumn, int** map);

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

	int test_case;
	int T;
	
	//freopen("input.txt", "r", stdin);
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
        cout << '#' << test_case << ' ';

        cin >> numN >> numW >> numH;
        
        int** map; // int map[numH][numW]; row index, column index
        map = (int**) malloc (numH * sizeof(int*));
        for (int i = 0; i < numH; i++)
            map[i] = (int*) malloc (numW * sizeof(int));

        for (int i = 0; i < numH; i++) {
            for (int j = 0; j < numW; j++) {
                cin >> map[i][j];
            }
        }

        // Let's solve by DFS
        minBlocks = numH * numW;
        process(map);

        // print result
        cout << minBlocks << '\n';
	}
	return 0;
}

void process(int** map) {
    for (int i = 0; i < numW; i++)
        process_(1, i, map);
}

void process_(int numTry, int theColumn, int** map) {
    // copied map
    int** newMap; // int newMap[numH][numW]; row index, column index
    newMap = (int**) malloc (numH * sizeof(int*));
    for (int i = 0; i < numH; i++)
        newMap[i] = (int*) malloc (numW * sizeof(int));

    // marked as remove map
    int** removeMap; // int newMap[numH][numW]; row index, column index
    removeMap = (int**) malloc (numH * sizeof(int*));
    for (int i = 0; i < numH; i++)
        removeMap[i] = (int*) malloc (numW * sizeof(int));

    // copy the map
    for (int i = 0; i < numH; i++) {
        for (int j = 0; j < numW; j++) {
            newMap[i][j] = map[i][j];
            removeMap[i][j] = 0;
        }
    }

    if (newMap[numH - 1][theColumn] != 0) { // if there is any block in this column, then proceed
        // find the topmost block in the column
        int theRow = -1;
        for (int i = 0; i < numH; i++) {
            if (newMap[i][theColumn] != 0) {
                theRow = i;
                break;
            }
        }

        // find other blocks need to be removed
        int* queueRow; //[numH * numW];
        int* queueColumn;
        int front = -1;
        int rear = -1;

        queueRow = (int*) malloc (numH * numW * sizeof(int));
        queueColumn = (int*) malloc (numH * numW * sizeof(int));

        if (front == -1)
            front = 0;
        
        rear++;
        queueRow[rear] = theRow;
        queueColumn[rear] = theColumn;

        removeMap[theRow][theColumn] = 1;

        while (front != -1 && front <= rear) { // while the queue is not empty
            int myRow = queueRow[front];
            int myColumn = queueColumn[front];
            front++; // dequeue

            int mySize = newMap[myRow][myColumn];
            if (mySize == 1) // value is 1: it breaks alone
                continue;

            int upperBound = 0, lowerBound = 0, leftBound = 0, rightBound = 0;
            
            upperBound = myRow - (mySize - 1);
            if (upperBound < 0)
                upperBound = 0;

            lowerBound = myRow + (mySize - 1);
            if (lowerBound > numH - 1)
                lowerBound = numH - 1;

            leftBound = myColumn - (mySize - 1);
            if (leftBound < 0)
                leftBound = 0;

            rightBound = myColumn + (mySize - 1);
            if (rightBound > numW - 1)
                rightBound = numW - 1;

            for (int i = myRow - 1; i >= upperBound; i--) {
                if (removeMap[i][myColumn] == 0) {
                    removeMap[i][myColumn] = 1;

                    if (newMap[i][myColumn] > 1) {
                        rear++;
                        queueRow[rear] = i;
                        queueColumn[rear] = myColumn;
                    }
                }
            }
            for (int i = myRow + 1; i <= lowerBound; i++) {
                if (removeMap[i][myColumn] == 0) {
                    removeMap[i][myColumn] = 1;

                    if (newMap[i][myColumn] > 1) {
                        rear++;
                        queueRow[rear] = i;
                        queueColumn[rear] = myColumn;
                    }
                }
            }
            for (int i = myColumn - 1; i >= leftBound; i--) {
                if (removeMap[myRow][i] == 0) {
                    removeMap[myRow][i] = 1;

                    if (newMap[myRow][i] > 1) {
                        rear++;
                        queueRow[rear] = myRow;
                        queueColumn[rear] = i;
                    }
                }
            }
            for (int i = myColumn + 1; i <= rightBound; i++) {
                if (removeMap[myRow][i] == 0) {
                    removeMap[myRow][i] = 1;

                    if (newMap[myRow][i] > 1) {
                        rear++;
                        queueRow[rear] = myRow;
                        queueColumn[rear] = i;
                    }
                }
            }
        }

        // remove map according to the removeMap info
        for (int i = 0; i < numH; i++) {
            for (int j = 0; j < numW; j++) {
                if (removeMap[i][j] == 1)
                    newMap[i][j] = 0;
            }
        }

        // move the blocks downward
        for (int i = 0; i < numW; i++) {
            int downmostBlankRow = -1;
            for (int j = numH - 1; j >= 0; j--) {
                if (downmostBlankRow == -1 && newMap[j][i] == 0) // first mark the blank space
                    downmostBlankRow = j;
                else if (downmostBlankRow != -1 && newMap[j][i] > 0) { // if the block need to be moved
                    newMap[downmostBlankRow][i] = newMap[j][i];
                    newMap[j][i] = 0;
                    downmostBlankRow--;
                }
            }
        }
    }
    //else ; // no need to proceed if there is no block in this column (no change)

    for (int i = 0; i < numH; i++)
        free(removeMap[i]);
    free(removeMap);

    if (numTry == numN) { // calculate remaining blocks
        int blocks = 0;
        for (int i = 0; i < numH; i++) { 
            for (int j = 0; j < numW; j++) {
                if (newMap[i][j] != 0)
                    blocks++;
            }
        }

        if (blocks < minBlocks)
            minBlocks = blocks;
    }
    else { // proceed
        // if there is no remaining block, then return
        bool noBlocksRemaining = true;
        for (int i = 0; i < numW; i++) {
            if (newMap[numH - 1][i] != 0) {
                noBlocksRemaining = false;
                break;
            }
        }

        // proceed if there is more blocks
        if (noBlocksRemaining == false) {
            for (int i = 0; i < numW; i++)
                process_(numTry + 1, i, newMap);
        }
        else // if there is no blocks remaining, then minBlocks becomes 0
            minBlocks = 0;
    }

    for (int i = 0; i < numH; i++)
        free(newMap[i]);
    free(newMap);
}