[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번 보다 많이 누를 수 없다는 조건이 없다면 어떻게 해야 할까??

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

 

 

소스코드

[ DFS ]

메모리 : 1988 KB , 시간 : 36ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 21
#define INF 987654321
using namespace std;

typedef pair<int, int> coin;

struct node {
    coin c1,c2;
    int cnt;
    
    node() { }
    node(coin _c1,coin _c2,int _cnt) : c1(_c1),c2(_c2),cnt(_cnt) { }
};

int n,m,ans;
char map[MAX][MAX];

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

vector<coin> coins;

bool is_out(int x,int y){
    if(x<0 || y<0 || x>=n || y>=m) return true;
    else return false;
}

void dfs(int x1,int y1,int x2,int y2,int cnt){
    /*----------[ 정답이 아닌 경우 ]----------*/
    // 버튼을 10번 보다 많이 누른 경우
    if(cnt > 10) return;
    
    // 현재 카운트가 최소값보다 크거나 같은 경우
    if(cnt >= ans) return;
    
    // 두 동전이 모두 밖으로 나간 경우
    if(is_out(x1,y1) && is_out(x2,y2)) return;
    
    
    /*----------[ 정답을 찾은 경우 ]----------*/
    // 두 동전 중, 하나만 밖으로 나간 경우
    if((!is_out(x1,y1) && is_out(x2,y2)) || (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(nx1,ny1,nx2,ny2,cnt+1);
    }
}

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'){
                coins.push_back(coin(i,j));
            }
        }
    }
    
    ans = INF;
    dfs(coins[0].first,coins[0].second,coins[1].first,coins[1].second,0);
    
    if(ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
    
    return 0;
}

 

[ BFS ]

메모리 : 88560 KB , 시간 : 140ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 21
#define INF 987654321
using namespace std;

typedef pair<int, int> coin;

struct node {
    coin c1,c2;
    int cnt;
    
    node() { }
    node(coin _c1,coin _c2,int _cnt) : c1(_c1),c2(_c2),cnt(_cnt) { }
};

int n,m,ans;
char map[MAX][MAX];

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

vector<coin> coins;

bool is_out(int x,int y){
    if(x<0 || y<0 || x>=n || y>=m) return true;
    else return false;
}

void bfs(){
    queue<node> q;
    q.push(node(coins[0],coins[1],0));
    
    while(!q.empty()){
        int x1 = q.front().c1.first;
        int y1 = q.front().c1.second;
        int x2 = q.front().c2.first;
        int y2 = q.front().c2.second;
        int cnt = q.front().cnt;
        q.pop();
        
        /*----------[ 정답이 아닌 경우 ]----------*/
        // 버튼을 10번 보다 많이 누른 경우
        if(cnt > 10) continue;
        
        // 두 동전이 모두 밖으로 나간 경우
        if(is_out(x1,y1) && is_out(x2,y2)) continue;
        
        
        /*----------[ 정답을 찾은 경우 ]----------*/
        // 두 동전 중, 하나만 밖으로 나간 경우
        if((!is_out(x1,y1) && is_out(x2,y2)) || (is_out(x1,y1) && !is_out(x2,y2))){
            cout << cnt << "\n";
            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;
            }
            
            q.push(node(coin(nx1,ny1),coin(nx2,ny2),cnt+1));
        }
    }
    cout << -1 << "\n";
}

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'){
                coins.push_back(coin(i,j));
            }
        }
    }
    
    bfs();
    
    return 0;
}