브루트 포스/브루트포스(재귀)

두 동전

4gats 2023. 5. 10. 21:11

https://www.acmicpc.net/problem/16197

 

16197번: 두 동전

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고,

www.acmicpc.net

경우의 수 4 ^ 10  그렇게 큰 수는 아니다

재귀 문제다!!

1. 불가능 한 경우

step == 11

두 동전 모두 떨어지는 경우

 

2. 정답

두 동전 '중'에서 하나만 떨어짐

 

3. 다음 경우

오른쪽, 왼쪽, 위 , 아래

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
string board[25];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int go(int step, int x1, int y1, int x2, int y2)
{
    if (step == 11) return -1;
    bool fall1 = false, fall2 = false;
 
    //범위를 벗어나면 동전이 떨어진 것
    if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) fall1 = true;
    if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) fall2 = true;
    if (fall1 && fall2) return -1;  // 2개가 동시에 떨어짐
    if (fall1 || fall2) return step; // 두 동전 중에 하나만 떨어짐
    int ans = -1;
    for (int k = 0; k < 4; k++)
    {
        int nx1 = x1 + dx[k];
        int ny1 = y1 + dy[k];
        int nx2 = x2 + dx[k];
        int ny2 = y2 + dy[k];
 
        //벽일 때 이동 x
        if (0 <= nx1 && nx1 < n && 0 <= ny1 && ny1 < m && board[nx1][ny1] == '#')
        {
            nx1 = x1;
            ny1 = y1;
        }
        if (0 <= nx2 && nx2 < n && 0 <= ny2 && ny2 < m && board[nx2][ny2] == '#') 
        {
            nx2 = x2;
            ny2 = y2;
        }
 
        int temp = go(step + 1, nx1, ny1, nx2, ny2);
 
        // 동전이 두 개 떨어짐 -> case 탈락
        if (temp == -1) continue;
 
        //정답의 최소값
        if (ans == -1 || ans > temp)
            ans = temp;
    }
    return ans;
}
 
int main()
{
 
    cin >> n >> m;
 
    int x1, y1, x2, y2;
    x1 = y1 = x2 = y2 = -1;
    
    // 이차원 char 배열 입력 방법
    for (int i = 0; i < n; i++)
    {
        cin >> board[i];
        for (int j = 0; j < m; j++)
        {
            if (board[i][j] == 'o')
            {
                if (x1 == -1)
                {
                    x1 = i;
                    y1 = j;
                }
                else
                {
                    x2 = i;
                    y2 = j;
                }
                board[i][j] = '.';  // 동전이 있는 칸은 빈칸이므로!
            }
        }
    }
 
    cout << go(0, x1, y1, x2, y2) << '\n';
 
    return 0;
}
 cs