[백준] 두 동전

https://www.acmicpc.net/problem/16197

16197번: 두 동전

우선 문제부터 요약하면, 

N x M의 보드에 빈칸, 벽, 그리고 두 동전이 위치하게 됩니다. 이 때 10번 이하로 두 동전을 같은 방향으로 1칸씩 이동시켜 하나의 동전만 떨어지게 하는 경우가 존재한다면 그 최소 이동횟수를 구하고, 10번 초과 또는 불가능한 경우에는 -1을 출력해야 하는 문제입니다.

 

<Solution>

10번이라는 조건이 주어졌기 때문에 재귀함수를 이용하여 충분히 구현할 수 있습니다. 

Return value가 있는 재귀함수이기 때문에, 마치 stack처럼 마지막 호출된 순서부터 차근차근 잘 빠져나올 수 있도록 구현해야 함에 주의하면 됩니다. 

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
char board[20+1][20+1]; // r, c

int moveR[4] = {1, -1, 0, 0};
int moveC[4] = {0, 0, 1, -1};

int solution(int curStep, int r1, int c1, int r2, int c2){
    int ans = 987654321;
    if(curStep ==11) return 987654321; 
    bool isFall1 = false, isFall2 = false;

    // check if coin is out
    if(r1 < 0 || r1 >= N || c1 < 0 || c1 >= M) isFall1 = true;
    if(r2 < 0 || r2 >= N || c2 < 0 || c2 >= M) isFall2 = true;
    
    if(isFall1 && isFall2) return 987654321; // both coins are out
    if(isFall1 || isFall2) return curStep;

    // move coin
    for(int i = 0; i<4; i++){
        int nr1 = r1 + moveR[i];
        int nc1 = c1 + moveC[i];
        int nr2 = r2 + moveR[i];
        int nc2 = c2 + moveC[i];

        // if there is wall don't move
        if(nr1 >= 0 && nr1 < N && nc1 >= 0 && nc1 < M && board[nr1][nc1] == '#'){
            nr1 = r1; nc1 = c1;
        }
        if(nr2 >= 0 && nr2 < N && nc2 >= 0 && nc2 < M && board[nr2][nc2] == '#'){
            nr2 = r2; nc2 = c2;
        }
        
        int tmp = solution(curStep+1, nr1, nc1, nr2, nc2);
        ans = min(tmp, ans);
    }
    return ans;
}

int main(){
    cin >> N >> M;

    for(int i = 0; i<N; i++){
        cin >> board[i];
    }

    // find position of coin
    vector<pair<int, int>> coinPosition;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(board[i][j] == 'o'){
                coinPosition.push_back({i,j}); // r,c
                board[i][j] = '.';
            }
        }
    }
    int tmpAns = solution(0, coinPosition[0].first, coinPosition[0].second, coinPosition[1].first, coinPosition[1].second);
    tmpAns = (tmpAns == 987654321) ? -1 : tmpAns;
    cout << tmpAns << endl;
    return 0;
}