[백준] 15653번. 구슬 탈출4

[문제]

 

www.acmicpc.net/problem/15653

15653번: 구슬 탈출 4

 

[풀이]

 

처음에는 DFS 방식으로 접근을 하였다.

하지만 생각을 해보니 DFS 함수의 탈출 조건을 설정할 수 없었다.

 

따라서 다른 방법을 생각하던 중 BFS 방식으로 풀어야겠다고 생각했다.

BFS 방식에서 처음 입력 값의 빨간, 파란 공의 위치를 시작으로 상,하,좌,우 방향으로 움직이도록 하였다.

이 때 파란 공이 골에 들어가거나, 이미 방문했던 위치라면 continue를 사용해 queue에 push하지 못하도록 하였다.

 

또한 움직인 빨간 공이 골에 들어갔다면 cnt를 return 하면서 BFS 함수를 끝내도록 하였다.

이러한 방식으로  queue가 empty가 아닐 때까지 반복하도록 하였다.

 

 

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <queue>

#define MAX 11

using namespace std;

struct pos{
    int x,y;
};

struct ball{
    int rx,ry;
    int bx,by;
    int cnt;
};

pos red,blue,goal;

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

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


pos move(int x, int y,int dir)
{

    while(1){
        x+=dx[dir];
        y+=dy[dir];
        if(x < 0 || y <0 || x >= N || y >= M || map[x][y] != 0 ){
            x -= dx[dir];
            y -= dy[dir];
            break;
        }
        if(goal.x==x && goal.y== y) break;
    }

    return {x,y};
}

int BFS()
{
    queue <ball> q;
    
    q.push({red.x,red.y,blue.x,blue.y,0});
    visited[red.x][red.y][blue.x][blue.y]=true;
    
    while(!q.empty()){

        int rx = q.front().rx;   int ry= q.front().ry;
        int bx = q.front().bx;   int by= q.front().by;
        int cnt = q.front().cnt;
        q.pop();
        
        for(int i=0;i<4;i++){
            
            pos tmp_red = move(rx,ry,i);
            pos tmp_blue = move(bx,by,i);
            
            
            if((tmp_blue.x == goal.x) &&(tmp_blue.y==goal.y))  continue;
            if((tmp_red.x==goal.x)&&(tmp_red.y == goal.y))    return cnt+1;
            
            if((tmp_blue.x==tmp_red.x)&&(tmp_blue.y==tmp_red.y)){
                
                if(i==0){
                    if(rx < bx)  tmp_blue.x++;
                    else    tmp_red.x++;
                }
                else if(i == 1){
                    if(ry < by)  tmp_red.y--;
                    else    tmp_blue.y--;
                }
                else if(i == 2){
                    if (rx < bx) tmp_red.x--;
                    else    tmp_blue.x--;
                }
                else if(i == 3){
                    if( ry< by) tmp_blue.y++;
                    else    tmp_red.y++;
                }
            }
            
            if(visited[tmp_red.x][tmp_red.y][tmp_blue.x][tmp_blue.y])   continue;
            visited[tmp_red.x][tmp_red.y][tmp_blue.x][tmp_blue.y]=true;
            q.push({tmp_red.x,tmp_red.y,tmp_blue.x,tmp_blue.y,cnt+1});
        }
    }
    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')    goal={i,j};
            else if(ch=='R')    red = {i,j};
            else if(ch=='B')    blue = {i,j};
        }
    }
    
    cout << BFS();
    
    return 0;
    
}