[백준 16197] 두 동전 C++

16197번: 두 동전

DFS, BFS

---

1. 문제 해결 아이디어

 

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

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

 

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

 

 

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

위 코드는 필수.

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

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

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

---

2. 코드

#include <iostream>
#include <queue>
#include <cstring>
 
#define pii pair<int, int>
 
using namespace std;
 
 
int N, M, result = 1e9+7;
int Map[21][21];    // 2 : 동전 위치   0 : 벽 위치   1 : 빈칸
vector< pii > startP;
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
 
void input(){
    // Map에서 벗어나는 경우는 -1로 설정
    memset(Map, -1, sizeof(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 > 10) cout << -1;
    else cout << result;
    
    return 0;
}
 

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

 

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