[DFS] 16197번 두 동전

16197번 두 동전

 

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

 

문제

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

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

 

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

예제 입력

1 2
oo

6 2
.#
.#
.#
o#
o#
##

6 2
..
..
..
o#
o#
##

5 3
###
.o.
###
.o.
###

5 3
###
.o.
#.#
.o.
###

 

예제 출력

1

4

3

-1

3

 

해결방법

DFS 탐색을 통해 모든 버튼의 경우를 탐색하는 부르트 포스 문제이다

시간 복잡도 : O(4^10)

 

사실 이 문제는 접근하기가 힘들었다

백트래킹으로 하려니 동전이 같은 노드를 1번 이상 방문할 수 있었다

또한 동전의 위치를 재귀마다 변경해야했다

 

⭐️ 솔루션 ⭐️

his130 님의 블로그

 

동전의 위치를 재귀마다 변경해야 하는 문제는 dfs의 파라미터로 x1, y1, x2, y2 를 전달하는 방법이었다

이렇게 한다면 실제 map 에서 동전의 위치를 변경하거나 전역변수를 변경하지 않아도됐다

 

사실 제일 이해가 안갔던 부분인 visited 배열에 대한 문제였다

부르트 포스에서 방문 노드를 체크하지 않는다면 두 노드끼리만 왔다 갔다 하는 문제가 발생한다

하지만 해당 문제에서는 버튼을 10번 보다 많이 누를 수 없다는 조건을 제시해줬다

 

따라서 만약 cnt > 10 이라면 dfs 문을 return 해주면 됐다

사실 아직 이 부분이 이해가 잘 되지 않는다...😭😭

 

만약 버튼을 10번 보다 많이 누를 수 없다는 조건이 없다면 어떻게 해야 할까??

백트래킹으로 접근을 할 수 있지 않을까??

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 21
#define INF 987654321
using namespace std;
typedef pair<int, int> node;

int n,m,ans;

char map[MAX][MAX];
bool visited[MAX][MAX];

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

vector<node> coin;

// 동전이 밖으로 나갔는지 확인하는 함수
bool is_out(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m) return true;
    else return false;
}

void dfs(int cnt,int x1,int y1,int x2,int y2){
    /*----------[ 정답이 아닌 경우 ]----------*/
    // 버튼을 10 번 보다 많이 누른 경우
    if(cnt > 10){
        return;
    }
    // 현재 카운트가 최소값보다 크거나 같은 경우
    if(cnt >= ans){
        return;
    }
    // 첫번째 동전 OUT , 두번째 동전 OUT
    if(is_out(x1,y1) && is_out(x2,y2)){
        return;
    }
    
    /*----------[ 정답을 찾은 경우 ]----------*/
    // 첫번째 동전 OUT , 두번째 동전 IN
    if(is_out(x1,y1) && !is_out(x2,y2)){
        ans = min(ans,cnt);
        return;
    }
    // 첫번째 동전 IN , 두번째 동전 OUT
    if(!is_out(x1,y1) && is_out(x2,y2)){
        ans = min(ans,cnt);
        return;
    }
    
    /*------[ 4개의 버튼에 대한 DFS 탐색 ]------*/
    for(int i=0; i<4; i++){
        int nx1 = x1 + dx[i]; int ny1 = y1 + dy[i];
        int nx2 = x2 + dx[i]; int ny2 = y2 + dy[i];
        
        if(map[nx1][ny1] == '#'){
            nx1 = x1;
            ny1 = y1;
        }
        if(map[nx2][ny2] == '#'){
            nx2 = x2;
            ny2 = y2;
        }
        dfs(cnt+1,nx1,ny1,nx2,ny2);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    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(node(i,j));
        }
    }
    
    ans = INF;
    dfs(0,coin[0].first,coin[0].second,coin[1].first,coin[1].second);
    
    if(ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
    
    return 0;
}