[BOJ] 16197번 : 두 동전 C++ 풀이

동전 2개가 주어질때, 하나의 동전만 떨어뜨리도록 적절히 움직이라고 한다.
최대 움직일 수 있는 횟수가 10회인점에 집중해보자. 매번 움직일 수 있는 경우의 수는 최대 4회이다. 

따라서 4^10번의 경우의 수를 전부 돌려 동전 중 하나만 밖으로 나가는 경우가 존재하는지 확인하면 된다. 움직인 방향을 vector로 관리하고, 이 vector에 들어있는 방향으로 시뮬레이션을 돌려 움직여보자. 이때 하나의 동전만 밖으로 나가는 값을 찾으면 된다. 

4^10번 만큼 경우의 수를 찾고, 시뮬레이션을 돌리는 최대 움직임이 10회이므로, 시간복잡도 O(4^10 * 10)에 문제를 해결할 수 있다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 1000000000
#define MOD 1000000009
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, M, answer = 11, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
char graph[30][30];
vector<int> dir;
vector<pii> start; 

void check_ans() {
    int x1 = start[0].X, y1 = start[0].Y;
    int x2 = start[1].X, y2 = start[1].Y;
    for (int i=0; i<dir.size(); i++) {
        if ((x1 == 0 || y1 == 0 || x1 == N+1 || y1 == M+1) && (x2 == 0 || y2 == 0 || x2 == N+1 || y2 == M+1)) return;
        if ((x1 < 0 || y1 < 0 || x1 > N+1 || y1 > M+1) || (x2 < 0 || y2 < 0 || x2 > N+1 || y2 > M+1)) return;
        
        int nx1 = x1 + dx[dir[i]], ny1 = y1 + dy[dir[i]];
        int nx2 = x2 + dx[dir[i]], ny2 = y2 + dy[dir[i]];
        if (graph[nx1][ny1] != '#') x1 = nx1, y1 = ny1;
        if (graph[nx2][ny2] != '#') x2 = nx2, y2 = ny2;
    }
    if (graph[x1][y1] == '-' && graph[x2][y2] != '-') answer = min(answer, (int)dir.size());
    if (graph[x1][y1] != '-' && graph[x2][y2] == '-') answer = min(answer, (int)dir.size());
}

void dfs(int s, int e) {
    if (s == e) return;
    check_ans();
    for (int i=0; i<4; i++) {
        dir.push_back(i);
        dfs(s+1, e);
        dir.pop_back();
    }
}

void init() {
    cin >> N >> M;
    for (int i=0; i<=N+1; i++) for(int j=0; j<=M+1; j++) graph[i][j] = '-';
    for (int i=0; i<N; i++) {
        string s;
        cin >> s;
        for (int j=0; j<M; j++) {
            graph[i+1][j+1] = s[j];
            if (s[j] == 'o') {
                start.push_back({i+1, j+1});
            }
        }
    }
    dfs(0, 11);
    if (answer == 11) answer = -1;
    cout << answer << '\n';
} 

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