[백준] 13459. 구슬 탈출

[문제]

 

www.acmicpc.net/problem/13459

13459번: 구슬 탈출

 

[풀이]

보드의 정보가 입력으로 주어지고 , 10번 이하의 움직임으로 빨간공이 빠져나갈 수 있으면 1을 출력하고 없으면 0을 출력한다.

 

먼저 입력으로 보드의 크기와 상태를 입력받았다.

장애물인 있는 좌표는 map에 -1을 저장하고, 구멍이 존재하는 좌표는 1을 저장했다.

 

DFS를 사용해서 풀었다. DFS 함수에서 인자 값으로 몇 번 움직였는지를 나타내는 cnt 를 넘겨주었다.

문제 조건에 의해 cnt가 10보다 크거나 같다면  return false를 하여 DFS 함수를 끝냈다.

 

DFS 함수에서는 for문을 통해 상,하,좌,우로 움직일 수 있도록 하였다. 

solve 함수는 공을 움직이는 함수로 인자로 전달받은 dir 방향으로 움직이도록  하였다.

 

문제의 조건들을 잘 신경써야 될 것 같다.

Ex )

 

1. 빨간공과 파란공 모두 탈출하면 실패

2. 파란공이 먼저 탈출하면 실패 

3. 보드의 한 칸에는 하나의 공만 존재할 수 있음

 

 

 

[코드]

 

시간 : 24ms

 

#include <iostream>
#define MAX 11

using namespace std;


struct pos{
    int x,y;
};

pos R,B;

int N,M;
int map[MAX][MAX]={0,};

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

int solve(int dir)
{
    int rx = R.x;
    int ry = R.y;
    
    while(1){
        if(map[rx][ry] != 0)    break;
        rx += dx[dir];
        ry += dy[dir];
    }
    
    int bx = B.x;
    int by = B.y;

    while(1){
        if(map[bx][by] != 0)    break;
        bx += dx[dir];
        by += dy[dir];
    }
    
    if(map[rx][ry] == 1 && map[bx][by] != 1)    return 1;
    else if(map[bx][by] == 1)   return -1;
    
    rx-= dx[dir];
    ry-= dy[dir];
    
    bx -= dx[dir];
    by -= dy[dir];
    
    if(rx == bx && ry == by){
        if(dir == 0 ) R.x > B.x ? rx++ : bx++ ;
        else if (dir == 1) R.y > B.y ? by-- : ry--;
        else if(dir == 2)   R.x > B.x ? bx-- : rx--;
        else if(dir == 3)   R.y > B.y ? ry++ : by++;

    }
    
    R={rx,ry};
    B={bx,by};
    
    return 0;
}

int DFS(int cnt)
{
    if(cnt >= 10 )  return 0;
    
    for(int i=0;i<4;i++){
        
        pos tmp_R = R;
        pos tmp_B = B;
        
        int res = solve(i);
        
        if(res==1 ) return 1;
        else if(res == -1)  continue;
        
        if(DFS(cnt+1) == 1)  return 1;
        
        R = tmp_R;
        B = tmp_B;
    }
    return -1;
}

int main(void)
{
    cin >> N >> M ;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            
            if (ch == '#')  map[i][j]=-1;
            else if(ch == 'O')  map[i][j] = 1;
            else if(ch == 'R')  {
                R.x = i;
                R.y = j;
            }
            else if(ch == 'B')  {
                B.x = i;
                B.y = j;
            }
        }
    }
    
    if(DFS(0) == 1) cout << "1";
    else cout << "0";
    
    return 0;
    
}