[algorithm] 백준 - 구슬탈출(2)

이 문제는 삼성 SW 기출 문제이다.

빨간 구슬을 구멍을 통해 빼내기 위해 기울이는 최소 횟수를 구해야 하므로 BFS로 풀었다.

 

문제에서 지켜야하는 조건이 있다.

1. 빨간 구슬과 파란 구슬이 같이 들어가면 실패

2. 빨간 구슬이 파란 구슬보다 먼저 들어가야 함

 

빨간 구슬과 파란 구슬을 이동하는 방향을 동일하게 설정해야하므로

방문 여부를 판단하는 배열의 인덱스도 빨간 구슬과 파란 구슬 모두의 방문유무를 설정해야한다.

이 방문 배열을 만드는 것을 생각하는 것이 가장 핵심이다.

 

그리고 큐에 넣을 때도 빨간 구슬과 파란 구슬의 위치, depth를 push해야한다.

따로따로 탐색하는 것이 아니라 같이 탐색해야한다!

 

참고로 중력에 의해 구슬의 위치가 정해지는데,

#####

#..R#

#...#

#O.B#

#####

이런 경우라고 가정했을 때,

중력에 의해 R의 위치가 기울이는 것과 상관 없이 아래로 내려가는 것을 걱정할 필요는 없다.

 

예외 상황을 생각해보자면,

오른쪽(0, 1)으로 기울였을 때,

이 경우 파란색이 구멍에 먼저 들어간다.

이런 경우들에 대한 예외처리를 해줘야 한다.

 

int directx[] = {0, 0, 1, -1};
int directy[] = {1, -1, 0, 0};

switch(i){
                   case 0: // (0,1)
                   node.red.second > node.blue.second ? by-- : ry--; break;
                   case 1: // (0, -1)
                   node.red.second < node.blue.second ? by++ : ry++; break;
                   case 2: // (1, 0)
                   node.red.first > node.blue.first ? bx-- : rx--; break;
                   case 3: // (-1, 0)
                   node.red.first < node.blue.first ? bx++ : rx++; break;
               }

 

따라서 이런 식으로 표현할 수 있다.

 

red가 구멍에 들어가고, 구멍에 들어가기 위해 진행되는 기울기의 횟수가 10개 이하가 되기 전까지 탐색을 하기 때문에

만약 blue가 구멍에 들어가더라도 그 탐색을 실패했다고 해서는 안된다.

즉 다른 방향으로 기울여줘야한다.

 

그리고 기울일 때 벽에 부딪힌 경우 좌표 위치를 이동 직전으로 되돌린다.

구멍에 위치할 경우 더이상 이동할 수 없도록 break 처리한다.

 

void move(int &x, int &y, int i){
    while(1){
        x += directx[i];
        y += directy[i];
        if(vertex[x][y] == 'O'){
            break;
        }
        if(vertex[x][y] == '#'){
            x -= directx[i];
            y -= directy[i];
            break;
        }
    }
}

 

전반적으로 코드로 표현하면 이렇다.

 

//구슬탈출(2)
#include <iostream>
#include <queue>
#include <string>
using namespace std;

int directx[] = {0, 0, 1, -1};
int directy[] = {1, -1, 0, 0};
bool visited[10][10][10][10];
string vertex[10];
int n, m, answer = -1;
pair<int,int> holl;
struct ball {
    int depth;
    pair<int,int> red, blue;
};
void move(int &x, int &y, int i){
    while(1){
        x += directx[i];
        y += directy[i];
        if(vertex[x][y] == 'O'){
            break;
        }
        if(vertex[x][y] == '#'){
            x -= directx[i];
            y -= directy[i];
            break;
        }
    }
}
void bfs(pair<int,int> pointRed, pair<int, int> pointBlue){
   queue<ball> q;
   q.push({0, pointRed, pointBlue});
   visited[pointRed.first][pointRed.second][pointBlue.first][pointBlue.second] = true;
   while(!q.empty()){
       ball node = q.front();
       q.pop();
        if(node.depth > 10){
            break;
        }
       if(node.red.first == holl.first && node.red.second == holl.second){
            answer = node.depth;
            break;
        }
       for(int i = 0; i < 4; i++){
           int rx = node.red.first;
           int ry = node.red.second;
           int bx = node.blue.first;
           int by = node.blue.second;
           move(rx, ry, i); move(bx, by, i);
           if(bx == holl.first && by == holl.second){
               continue;
           }
           if(rx == bx && ry == by){
               switch(i){
                   case 0:
                   node.red.second > node.blue.second ? by-- : ry--; break;
                   case 1:
                   node.red.second < node.blue.second ? by++ : ry++; break;
                   case 2:
                   node.red.first > node.blue.first ? bx-- : rx--; break;
                   case 3:
                   node.red.first < node.blue.first ? bx++ : rx++; break;
               }
           }
           if(!visited[rx][ry][bx][by]){
               visited[rx][ry][bx][by] = true;
               q.push({node.depth + 1, {rx,ry}, {bx, by}});
           }
       }
   }
}
int main(void){
    cin >> n >> m;
    pair<int,int> pointRed, pointBlue;
    for(int i = 0; i < n; i++){
        cin >> vertex[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j< m; j++){
            if(vertex[i][j] == 'R'){
                pointRed = {i,j};
            }
            if(vertex[i][j] == 'B'){
                pointBlue = {i,j};
            }
            if(vertex[i][j] == 'O'){
                holl = {i,j};
            }
        }
    }
    bfs(pointRed, pointBlue);
    cout << answer;
}