[백준] 16197번 두 동전

 

[적용한 알고리즘]

브루트포스, 재귀

 

[아이디어]

경우의 수가 4^10개니까 다 해봐도 상관없겠다.

 

[생각의 흐름 / 절차] 

1. 각 동전의 좌표를 알아낸다.

2. 검사해야할 것들을 살펴본다. (탈출 조건)

1) 혹시 옮긴 횟수가 10번을 넘어가지는 않는가?

2) 지금 좌표에서 1개만 떨어지는 상황인가?

2-1) 1개만 떨어지는 상황이면 지금까지 반복했던 횟수를 리턴한다.

2-2) 둘다 떨어진다면 -1을 리턴한다.

3) 가려고 하는 방향에 벽이 있다면? 

4) ans에는 항상 최소가 들어가도록 한다. 

 

 

[교훈]

재귀함수는 여전히 나한테 어렵다. 머리가 안좋은건가?

 

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

char map[21][21];
int n, m;
int x[2], y[2];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, 1, -1};

int go(int x1, int y1, int x2, int y2, int cnt){
    bool out1 = false;
    bool out2 = false;

    if (cnt > 10) return -1;

    if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) out1 = true;
    if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) out2 = true;
    if (out1 && out2) return -1;
    if (out1 || out2) return cnt;

    int ans = -1;

    for (int k = 0; k < 4; k++){
        int nx1 = x1 + dirx[k];
        int ny1 = y1 + diry[k];
        int nx2 = x2 + dirx[k];
        int ny2 = y2 + diry[k];

        if (0 <= nx1 && nx1 < n && 0 <= ny1 && ny1 < m && map[nx1][ny1] == '#') {
            nx1 = x1;
            ny1 = y1;
        }
        if (0 <= nx2 && nx2 < n && 0 <= ny2 && ny2 < m && map[nx2][ny2] == '#') {
            nx2 = x2;
            ny2 = y2;
        }

        int nxt = go(nx1, ny1, nx2, ny2, cnt + 1);
        if (nxt == -1) continue;
        if (ans == -1 || ans > nxt){
            ans = nxt;
        }
    }
    return ans;
}

int main(){
    scanf("%d %d", &n, &m);

    int pos = 0;
    for (int i = 0; i < n; i++){
        scanf("%s", map[i]);
        for (int j = 0; j < m; j++){
            if (map[i][j] == 'o'){
                x[pos] = i;
                y[pos] = j;
                pos++;
            }
        }
    }
    printf("%d", go(x[0], y[0], x[1], y[1], 0));

    return 0;
}