Algorithm/BOJ

[백준 16197] 두 동전 C++

Henu 2021. 6. 26. 04:09
 

16197번: 두 동전

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

www.acmicpc.net

DFS, BFS


1. 문제 해결 아이디어

 

  • 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
  • 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
  • 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
  • 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

문제에 나와있는 그대로 구현했다.

 

DFS를 통해서 잘못된 길에 들어선 뒤에 백트래킹이 가능하게 구현을 하였다.

 

 

memset(Map, -1, sizeof(Map)); 

위 코드는 필수.

전역 변수 Map은 모두 0으로 자동 초기화가 된다.

다음 이동할 위치가 Map을 벗어난다면 동전이 떨어져야 하는데

해당 위치의 Map에 입력된 수가 0 이기 때문에 벽으로 인식하고 해당 동전의 위치는 그대로 있게 된다.


2. 코드

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
#include <iostream>
#include <queue>
#include <cstring>
 
#define pii pair<intint>
 
using namespace std;
 
 
int N, M, result = 1e9+7;
int Map[21][21];    // 2 : 동전 위치   0 : 벽 위치   1 : 빈칸
vector< pii > startP;
int dr[4= {001-1}, dc[4= {1-100};
 
void input(){
    // Map에서 벗어나는 경우는 -1로 설정
    memset(Map, -1sizeof(Map));
    
    cin >> N >> M;
    string str;
    for(int i = 1; i <= N; i++){
        cin >> str;
        for(int j = 0; j < M; j++){
            if(str[j] == 'o'){
                Map[i][j+1= 2;
                startP.push_back({i, j+1});
            }
            else if(str[j] == '#') Map[i][j+1= 0;
            else Map[i][j+1= 1;
        }
    }
}
 
bool isOut(const pii &A){
    if(A.first < 1 || A.first > N || A.second < 1 || A.second > M) return true;
    return false;
}
 
void dfs(pii A, pii B, int cnt){
    // 현재 result보다 cnt가 크다면 더이상의 탐색은 불필요
    if(result < cnt) return;
    
    // cnt 가 10보다 커지면 result값 갱신
    if(cnt > 10){
        result = min(result, cnt);
        return;
    }
    
    // 둘 다 떨어졌으면 되돌아감
    if(isOut(A) && isOut(B)) return;
    // 하나만 떨어졌으면 result를 최소 cnt값으로 교체
    else if((isOut(A) && !isOut(B)) || (!isOut(A) && isOut(B))){
        result = min(result, cnt);
        return;
    }
    
    for(int i = 0; i < 4; i++){
        pii An = {A.first + dr[i], A.second + dc[i]};
        pii Bn = {B.first + dr[i], B.second + dc[i]};
        if(!Map[An.first][An.second]) An = A;
        if(!Map[Bn.first][Bn.second]) Bn = B;
        
        dfs(An, Bn, cnt+1);
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    input();
    dfs(startP[0], startP[1], 0);
    
    if(result > 10cout << -1;
    else cout << result;
    
    return 0;
}
 
cs

 

다른 사람들 풀이 대부분이 BFS를 사용한 풀이다.

 

DFS풀이에요 참고해주세요!