# 16197. 두 동전

관련 알고리즘 : 그래프 탐색, 백트래킹

 

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

16197번: 두 동전

---

문제 풀이

 

문제의 조건을 보면,

• NxM 크기의 보드
• 동전 2개 ( 서로 다른 빈 칸에 존재)
• 각 보드의 칸에 동전 / 벽 / 혹은 빈 칸 존재
• 상, 하, 좌, 우 이동 가능한 4개의 버튼
• 버튼으로 동전 2개 동시조작 ( 동전은 동시에 같이 이동 )
  • 이동하려는 칸이 벽일 시 => 동전 이동 X
  • 이동하려는 칸이 없을 시 => 동전 떨어짐

두 동전 중 하나만 보드에 떨어뜨려야 하며, 최소 버튼을 몇 번 눌러야 하는지가 문제에서 원하는 조건이다.

 

버튼을 눌러 동전을 굴렸을 때, 발생할 수 있는 상황은 다음 3가지이다.

• 2개의 동전 중, 2개 모두 보드 밖으로 떨어지는 경우
• 2개의 동전 중, 2개 모두 보드 내에 존재하는 경우 
• 2개의 동전 중, 1개만 보드 밖으로 떨어지는 경우 ( 문제에서 원하는 경우 )

해당되는 모든 경우의 수를 탐색하여 문제를 해결할 수 있었다.

 

---

C++ 코드

 

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

using namespace std;

int n, m;
int ans; // 답
char board[20][20]; // 보드

vector<pair<int, int>> coin; // 동전 위치 저장용 vector

int dx[] = { 0, 0, 1, -1 }; // 좌우 이동
int dy[] = { 1, -1, 0, 0 }; // 상하 이동

bool out(int a, int b) // 동전이 보드 밖으로 이탈 시 false 반환
{
    if (a < 0 || b < 0 || a >= n || b >= m) return true;
    return false;
}

void move(int coin1_x, int coin1_y, int coin2_x, int coin2_y, int cnt, int dir) // 동전 움직이기: move(동전1x, 동전1y, 동전2x, 동전2y, 버튼 누른 횟수, 방향)
{
    if (ans < cnt) 
        return; // 다른 경우의 결과보다 더 많이 버튼을 눌러야 한다면 => 최솟값이 이미 아니므로 탈출

    if (cnt > 10) // 이동 횟수 10번 이상일 경우                      
    {
        ans = min(ans, cnt); // ans값 갱신 후 탈출
        return;
    }

    int nx1 = coin1_x + dx[dir];
    int ny1 = coin1_y + dy[dir];
    int nx2 = coin2_x + dx[dir];
    int ny2 = coin2_y + dy[dir];

    if (out(nx1, ny1) == true && out(nx2, ny2) == true) // 2개 모두 떨어질 시
        return; 
    else if (out(nx1, ny1) == true && out(nx2, ny2) == false) // 2개 중 1개만 떨어질 시
    {
        ans = min(ans, cnt); // 최솟값 갱신
        return; // 결과 도출
    }
    else if (out(nx1, ny1) == false && out(nx2, ny2) == true)
    {
        ans = min(ans, cnt);
        return;
    }

    if (board[nx1][ny1] == '#') // 이동한 곳이 벽에 막힌 곳일 시, 이동 불가
    {
        nx1 = coin1_x;
        ny1 = coin1_y;
    }
    if (board[nx2][ny2] == '#')
    {
        nx2 = coin2_x;
        ny2 = coin2_y;
    }

    for (int i = 0; i < 4; i++) // 위 조건 모두 통과 시, 진행 
    {
        move(nx1, ny1, nx2, ny2, cnt + 1, i);
    }
}

void solve()
{
    ans = 99999999; // 최솟값과 비교해야 하므로 큰 수로 설정

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 'o') coin.push_back(make_pair(i, j)); // 동전 위치 저장
        }
    }
    
    for (int i = 0; i < 4; i++)
    {
        int x1 = coin[0].first;
        int y1 = coin[0].second;
        int x2 = coin[1].first;
        int y2 = coin[1].second;

        move(x1, y1, x2, y2, 1, i);
    }

    if (ans > 10)
        ans = -1;

    cout << ans << "\n";
}

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

    solve();

    return 0;
}