[BruteForce] 백준 16197: 두 동전

16197번: 두 동전 (acmicpc.net)

16197번: 두 동전

 

재귀함수를 이용한 brute force 문제. 동전은 무조건 2개이고, 가능한 입력 방향은 4개이다. 다음과 같은 구조를 생각하면서 재귀함수를 작성하였다.

 

 

사실 대단히 어려운 문제가 아니지만 42% 정도에서 계속 오류가 나서 고생을 했는데, 알고 보니 내가 base case 조건을 [버튼을 10번 보다 많이 누를 것]이 아닌 [버튼을 10번 이상 누를 것]으로 오독해서 생긴 문제였다. 재귀함수를 짤 때는 항상 base case를 확실히 고려해야 한다는 것을 다시 한 번 느끼게 해 준 문제였다.

 

전체 코드 첨부하고 마친다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int answer = -1;

void recursiveCall(int firstBallRow, int firstBallCol, int secondBallRow, int secondBallCol, int dir, int movedNum, vector<vector<int>> &board)
{
    if (movedNum > 10)
        return;

    bool isFirstBallOut = false;
    bool isSecondBallOut = false;

    int nextFirstBallRow = firstBallRow;
    int nextFirstBallCol = firstBallCol;
    int nextSecondBallRow = secondBallRow;
    int nextSecondBallCol = secondBallCol;
    switch (dir)
    {
    case 0: // up
        if (firstBallRow + 1 >= N)
        {
            isFirstBallOut = true;
        }
        else
        {
            if (board[firstBallRow + 1][firstBallCol] == 0)
            {
                nextFirstBallRow++;
            }
        }

        if (secondBallRow + 1 >= N)
        {
            isSecondBallOut = true;
        }
        else
        {
            if (board[secondBallRow + 1][secondBallCol] == 0)
            {
                nextSecondBallRow++;
            }
        }
        break;
    case 1: // down
        if (firstBallRow - 1 < 0)
        {
            isFirstBallOut = true;
        }
        else
        {
            if (board[firstBallRow - 1][firstBallCol] == 0)
            {
                nextFirstBallRow--;
            }
        }

        if (secondBallRow - 1 < 0)
        {
            isSecondBallOut = true;
        }
        else
        {
            if (board[secondBallRow - 1][secondBallCol] == 0)
            {
                nextSecondBallRow--;
            }
        }
        break;
    case 2: // left
        if (firstBallCol - 1 < 0)
        {
            isFirstBallOut = true;
        }
        else
        {
            if (board[firstBallRow][firstBallCol - 1] == 0)
            {
                nextFirstBallCol--;
            }
        }

        if (secondBallCol - 1 < 0)
        {
            isSecondBallOut = true;
        }
        else
        {
            if (board[secondBallRow][secondBallCol - 1] == 0)
            {
                nextSecondBallCol--;
            }
        }
        break;
    case 3: // right
        if (firstBallCol + 1 >= M)
        {
            isFirstBallOut = true;
        }
        else
        {
            if (board[firstBallRow][firstBallCol + 1] == 0)
            {
                nextFirstBallCol++;
            }
        }

        if (secondBallCol + 1 >= M)
        {
            isSecondBallOut = true;
        }
        else
        {
            if (board[secondBallRow][secondBallCol + 1] == 0)
            {
                nextSecondBallCol++;
            }
        }
        break;
    }

    if (!isFirstBallOut && !isSecondBallOut)
    {
        for (int i = 0; i < 4; i++)
        {
            recursiveCall(nextFirstBallRow, nextFirstBallCol, nextSecondBallRow, nextSecondBallCol, i, movedNum + 1, board);
        }
    }
    else if (isFirstBallOut && isSecondBallOut)
    {
        return;
    }
    else
    {
        if (answer == -1)
            answer = movedNum;
        else
            answer = min(answer, movedNum);
    }
}

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

    cin >> N >> M;

    vector<vector<int>> board(N, vector<int>(M));

    string input;
    const char *charArr;
    int firstBallRow;
    int firstBallCol;
    int secondBallRow;
    int secondBallCol;
    bool isFirstBall = true;
    for (int r = 0; r < N; r++)
    {
        cin >> input;
        charArr = input.c_str();

        for (int c = 0; c < M; c++)
        {
            if (charArr[c] == 'O' || charArr[c] == 'o' || charArr[c] == '.')
            {
                board[r][c] = 0;
                if (charArr[c] == 'O' || charArr[c] == 'o')
                {
                    if (isFirstBall)
                    {
                        firstBallRow = r;
                        firstBallCol = c;
                        isFirstBall = false;
                    }
                    else
                    {
                        secondBallRow = r;
                        secondBallCol = c;
                    }
                }
            }
            else
            {
                board[r][c] = 1;
            }
        }
    }

    for(int i=0;i<4;i++)
    {
        recursiveCall(firstBallRow, firstBallCol, secondBallRow, secondBallCol, i, 1, board);
    }

    cout<<answer;
}