16197번

16197번 - 두 동전

동전을 최대 4가지 방향에 대해서 10번까지 던질 수 있으므로, 최악의 경우 O(4^10) 이 된다. 따라서 완전탐색으로 주어진 시간 내에 문제해

결을 할 수 있다. 두 가지 동전을 동시에 이동시키면서 조건에 따라서 나누었다. 벽이 있는 경우와 벽이 없는 경우 조건문을 이용해서 나누었

다. 그리고 기저 조건에서는 지금 구한 정답보다 더 던졌는지, 10번 넘게 던졌는지, 둘다 범위를 넘는지, 하나만 범위를 넘는지를 체크해준다.

만약 정답을 구할 수 없는 경우에는 ans 가 초기값인 INF 로 설정되어 있으므로, -1로 바꿔준 후 정답을 출력하면 된다.

<정답 코드>

#include<iostream>
using namespace std;
#define INF 987654321
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int N, M;
char map[31][31];
int ans =INF;
bool check_range(int x, int y)
{
    if (x >= 0 && y >= 0 && x < N && y < M)
        return true;
    else
        return false;
}
void dfs(int k,int x1, int y1, int x2, int y2)
{
    if (k > 10)
        return;
 
    if (k >= ans)
        return;
 
    if (!check_range(x1, y1) && !check_range(x2, y2))
        return;
 
    if (check_range(x1,y1) && !check_range(x2,y2))
    {
        ans = k;
        return;
    }
 
    if (!check_range(x1, y1) && check_range(x2, y2))
    {
        ans = k;
        return;
    }
 
 
    for (int d = 0; d < 4; d++)
    {
        int nx1 = x1 + dx[d];
        int ny1 = y1 + dy[d];
        int nx2 = x2 + dx[d];
        int ny2 = y2 + dy[d];
    
        if(map[nx1][ny1]!='#' && map[nx2][ny2]!='#')
            dfs(k + 1, nx1, ny1, nx2, ny2);
 
        if (map[nx1][ny1] == '#' && map[nx2][ny2] != '#')
            dfs(k + 1, x1, y1, nx2, ny2);
 
        if (map[nx1][ny1] != '#' && map[nx2][ny2] == '#')
            dfs(k + 1, nx1, ny1, x2, y2);
 
    }
 
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int x1, y1, x2, y2, cnt = 0;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 'o') {
                if (cnt == 0)
                {
                    x1 = i, y1 = j;
                    cnt++;
                }
                else
                {
                    x2 = i, y2 = j;
                }
            }
        }
    }
 
 
    dfs(0,x1, y1, x2, y2);
 
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
    
 
 
    return 0;
}