[Algorithm] 백준 16197 - 두 동전, C++, DFS

16197번: 두 동전

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int boardH, boardW;
char board[21][21];
int moveX[4] = {0, 0, 1, -1};
int moveY[4] = {1, -1, 0, 0};
vector<pair<int, int>> coinPos;  // height, weight
int answer = 20;

bool isCoinOut(const pair<int, int>& coin){
    if(coin.first < 0 || coin.second < 0 || coin.first >= boardH || coin.second >= boardW)
        return true;
    
    return false;
}

bool isWallStuck(const pair<int, int>& coin){
    if(board[coin.first][coin.second] == '#')
        return true;

    return false;
}

void moveCoin(pair<int, int> coin1, pair<int, int> coin2, int moveCount, int direction){
    // not answer
    if(moveCount > 10)  return;
    if(answer < moveCount)  return;

    // Next Position
    pair<int, int> coin1Next = make_pair(coin1.first + moveY[direction], coin1.second + moveX[direction]);
    pair<int, int> coin2Next = make_pair(coin2.first + moveY[direction], coin2.second + moveX[direction]);

    bool is1Stuck = isWallStuck(coin1Next);
    bool is2Stuck = isWallStuck(coin2Next);
    bool is1Out = isCoinOut(coin1Next);
    bool is2Out = isCoinOut(coin2Next);

    // stuck can't move
    if(is1Stuck)    coin1Next = coin1;
    if(is2Stuck)    coin2Next = coin2;

    // not answer
    if(is1Out && is2Out)    return;
    if(is1Stuck && is2Stuck)    return;

    // only one coin out
    if(is1Out ^ is2Out){
        answer = min(answer, moveCount);
        return;
    }

    // no return -> move next
    for(unsigned dir = 0; dir < 4; dir++)
        moveCoin(coin1Next, coin2Next, moveCount+1, dir);
}


int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> boardH >> boardW;

    for(unsigned h = 0; h < boardH; h++){
        for(unsigned w = 0; w < boardW; w++){
            char input;
            cin >> input;

            if(input == 'o')
                coinPos.push_back(make_pair(h, w));
            
            board[h][w] = input;
        }
    }

    // solve
    for(unsigned dir = 0; dir < 4; dir++)
        moveCoin(coinPos[0], coinPos[1], 1, dir);

    // output
    if(answer > 10)
        cout << "-1\n";
    else
        cout << answer << '\n';

    return 0;
}

---

 오랜만에 알고리즘 문제를 잡고 풀이하는데 처음에 봤을 때 '이건 BFS 문제인가?' 해서 했다가 틀렸습니다를 한번 받은 문제입니다. 일단 평면 위 이동이라 BFS라 생각했는데 visit 체크가 조금 번거롭기도 하고 visit 체크 없이 하면 큐에 들어가는 것들이 너무 많아져서 DFS로 선회하고 풀이를 했습니다.

 

 DFS로 풀이할때는 여러 조건들을 고려해야 하는데 그 사항들이 아해 있습니다.

- 두 동전 다 나가게 되었다

- 두 동전 다 벽에 부딛히게 되었다

- 한개의 동전만 나가게 되었다

- 두 동전 다 이동을 했다

- 10번 이상 이동했는가 (문제 조건)

 

 일단 저기서 두 동전 다 벽에 부딛히게 되었다를 고려하지 않아도 풀이는 가능하지만 시간적인 이점을 가져오기 위해서 검사를 해주면 좋습니다.

 그리고 두 동전 다 나가면 정답에 해당되지 않으니 return을 하고 둘 다 무사히 이동을 했다면 다음 지점에서 4방향으로 함수 콜을 해주면 됩니다. 

 마지막으로 한개만 나가게 되었다면 그때 정답 비교를 해서 count가 작은 답을 저장해주면 됩니다.