백준의 두 동전(16197) 문제이다.

( 문제 바로가기 )


[ 문제풀이 ]

1. 이 문제는 동전이 갈 수 있는 모든 방향에 대해서 탐색해 보고 문제의 조건대로, 2개의 동전 중 하나만 떨어지는 경우가

   존재한다면, 버튼을 몇 번 누르면 되는지 출력하면 되는 문제이다.

2. 먼저 나는 입력 받을 때, 2개의 동전의 위치를 모두 Vector에 저장해주었다.

3. 이후, 상하좌우 4개의 방향으로 모두 2개의 동전을 동시에 움직여 주었다.

4. 동전의 움직일 때 생각해줘야 할 조건은 다음과 같다.

   1. 선택한 방향으로 동전을 굴렸을 때, 2개의 동전 모두 맵 밖으로 떨어진다면 ?

   2. 선택한 방향으로 동전을 굴렸을 때, 2개 중 한 개만 떨어진다면?

   3. 선택한 방향으로 동전을 굴렸을 때, 2개의 동전 모두 떨어지지 않는다면?

   위의 3가지만 잘 유의하면서 문제를 풀어주면 된다.

   먼저 1번 조건부터 살펴보겠다.

   2개의 동전이 모두 밖으로 떨어진다면, 그 방향으로는 진행하면 안된다는 의미이다.

   ( 이 설명을 보다 코드적으로 이해하고 싶다면 밑에 코드에서 Move() 함수를 참고 할 것.

     Move(1번동전의 x좌표, 1번동전의 y좌표, 2번동전의 x좌표, 2번동전의 y좌표, 버튼누른횟수, 현재 진행하고 있는 방향)

   그대로 동전을 굴리는 것을 끝내버리고, 다른 방향으로 다시 시도를 하면 되는 것이다.

   2번 조건이다. 이 경우에는 버튼을 누른 횟수를 기존의 값과 비교해서 최소값을 도출해 내고 종료시키면 된다.

   3번 조건의 경우, 동전들의 좌표를 움직여 주고, 다음 진행방향으로 계속 진행해 주면 된다.

5. 문제의 조건중 이러한 조건이 있다. " 버튼을 누른 횟수가 10회 이상이거나, 동전이 떨어질 수 없다면 -1을 출력하라"

   이 중에서, 버튼을 누른 횟수가 10회 이상인 경우에는 어떻게 쉽게 구현 할 수 있을 것 같지만, 동전을 떨어뜨릴 수 없는

   경우는 조금 막막할 수 있지만, 따로 구현할 필요가 없다.

   예를 들어서, 15회 만에 동전을 떨어뜨릴 수 있는 경우와, 동전을 어떻게 해도 떨어지지 않는 경우가 있다고 생각해보자.

   위의 2경우의 답은 동일하게 -1일 것이다. 즉, 10회 이상이거나 라는 말 안에 동전을 떨어질 수 없는 경우에도 포함되있다고

   생각해도 무방하다.


[ 소스코드 ]

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, M, Answer;
char MAP[MAX][MAX];
 
vector<pair<intint>> Coin;
 
int dx[] = { 001-1 };
int dy[] = { 1-100 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    Answer = 99999999;
 
    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') Coin.push_back(make_pair(i, j));    // 동전의 좌표를 Vector에 장
        }
    }
}
 
bool Range_Over(int a, int b)     // 동전이 맵 밖으로 나가는 경우 false를 반환, 반대의 경우 true를 반환하는 함수
{
    if (a < 0 || b < 0 || a >= N || b >= M) return true;
    return false;
}
 
void Move(int x, int y, int xx, int yy, int Cnt, int dir)    // 실질적으로 동전을 움직이는 함수(동전1x, 동전1y, 동전2x, 동전2y, 버튼누른횟수, 진행방)향
{
    if (Answer < Cnt) return;            // 기존의 횟수보다 더 많이 버튼을 눌렸다면 더 이상 해볼 필요가 없다. (최소값이 아니므로)
    if (Cnt > 10)                        // 10번 이상인 경우, 더이상 진행할 필요가 없다.
    {
        Answer = Min(Answer, Cnt);        // 기존의 횟수와 비교해서 값을 갱신만 시켜주고 그대로 종료.
        return;            
    }
 
    int nx = x + dx[dir];                
    int ny = y + dy[dir];
    int nxx = xx + dx[dir];
    int nyy = yy + dy[dir];
 
    if (Range_Over(nx, ny) == true && Range_Over(nxx, nyy) == truereturn;    // 두 동전 모두 떨어진다면 그대로 종료.
    else if (Range_Over(nx, ny) == true && Range_Over(nxx, nyy) == false)    // 한 동전만 떨어지는 경우
    {
        Answer = Min(Answer, Cnt);
        return;
    }
    else if (Range_Over(nx, ny) == false && Range_Over(nxx, nyy) == true)     // 한 동전만 떨어지는 경우 
    {
        Answer = Min(Answer, Cnt);
        return;
    }
 
    if (MAP[nx][ny] == '#')        // 동전이 벽에 막힌 경우 동전은 움직일 수 없음.
    {
        nx = x;
        ny = y;
    }
    if (MAP[nxx][nyy] == '#')
    {
        nxx = xx;
        nyy = yy;
    }
 
    for (int i = 0; i < 4; i++)        // 이 다음 진행방향으로 
    {
        Move(nx, ny, nxx, nyy, Cnt + 1, i);
    }
}
 
void Solution()
{
    for (int i = 0; i < 4; i++)
    {
        int x = Coin[0].first;
        int y = Coin[0].second;
        int xx = Coin[1].first;
        int yy = Coin[1].second;
 
        Move(x, y, xx, yy, 1, i);
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    if (Answer > 10) Answer = -1;
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}
cs

  


'[ BOJ Code ] > # BOJ -' 카테고리의 다른 글

[ 백준 2589 ] 보물섬 (C++)  (0) 2018.12.23
[ 백준 11057 ] 오르막 수 (C++)  (0) 2018.12.17
[ 백준 15685 ] 드래곤 커브 (C++)  (4) 2018.12.14
[ 백준 2234 ] 성곽 (C++)  (0) 2018.12.14
[ 백준 9461 ] 파도반 수열 (C++)  (0) 2018.12.14

+ Recent posts