[BOJ 13460] 구슬 탈출2

문제출처

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

문제풀이

 삼성 역량테스트 기출문제 입니다.

문제에서 원하는 답은 보드를 상,하,좌,우 방향으로 기울였을때 빨간구슬만을 구멍으로 빼낼 수 있는 최소횟수입니다. 이때, 파란구슬은 빠지면 안되고 보드는 총 10번 이하로 움직여야 합니다. 출력은 목적을 달성하는 최소횟수이고 파란구슬이 빠지거나 보드를 10번이상 움직였다면 -1을 출력하면 됩니다.

문제이해를 위해 예제를 따라해보면 더 쉽게 이해하실 수 있습니다.

예제를 따라하면 처음에 왼쪽으로 움직이고 다음번에 오른쪽으로 움직인경우 구슬의 위치가 같은 것을 알 수 있습니다. 또한 같은 방향으로 반복적으로 움직여도 구슬의 위치에는 영향을 받지 않는다는 것을 알 수 있습니다.

즉, 같은방향 혹은 이전방향과 반대방향으로 움직일 경우는 제외해도 됩니다. (구슬의 위치가 같다면 이러한 경우에 해당됩니다.)

문제풀이 과정은 다음과 같습니다.

1.  빨간공을 움직입니다.

2. 파란공을 움직입니다.

3. 파란공이 구멍으로 빠진경우 잘못된 경우이므로 제외합니다.

4. 빨간공과 파란공의 위치가 중복된 경우 공의 위치를 재조정합니다.

    만약 빨간공이 3칸, 파란공이 2칸이동했다면 빨간공의 위치를 이동방향 기준으로 1번 뒤로 되돌립니다.

    예를 들어 # . . R B #일때 왼쪽으로 기울인다면 공의 위치가 겹치기 때문에 # (R,B) . . . # 와 같은 상태입니다.

    이 경우 빨간공이 2칸, 파란공이 3칸움직였기 때문에 파란공을 오른쪽으로 1번 되돌려야 정상적인 좌표를 가지게 됩니다.

5. 이과정을 반복하면서 빨간공만 빠지고 움직인 횟수가 10번이내라면 횟수를 출력하고 이외의 경우에는 -1을 출력합니다.

소스코드

//
//  main.cpp
//  BOJ_13460(구슬탈출2)
//
//  Created by seungwoo on 08/10/2019.
//  Copyright © 2019 seungwoo. All rights reserved.
//
#include <iostream>
#include <queue>
#define MAX 10
using namespace std;
int n, m, srx, sry, sbx, sby;
char board[MAX][MAX+1]; // x축 공간을 +1한 이유는 char형시 널문자를 저장하기 위함
const char BLOCK     = '#';
const char HOLE      = 'O';
const char RED_BALL  = 'R';
const char BLUE_BALL = 'B';
struct BALL {
    int ry, rx, by, bx, moveCnt;
};
 
int bfs() {
    const int dy[] = {0, 0, 1, -1};
    const int dx[] = {1, -1, 0, 0};
    bool visit[MAX][MAX][MAX][MAX] = {0,};
    queue<BALL> q;
    q.push({sry, srx, sby, sbx, 0});
    visit[sry][srx][sby][sbx] = 1;
    
    while (!q.empty()) {
        BALL curBall = q.front();
        q.pop();
        
        // 7. 빨간공이 현재 구멍으로 빠졌을 경우 정답 return
        if (board[curBall.ry][curBall.rx] == HOLE) {
            return curBall.moveCnt;
        }
        
        for (int i=0; i<4; i++) {
            int nry = curBall.ry;
            int nrx = curBall.rx;
            int nby = curBall.by;
            int nbx = curBall.bx;
            int moveRedCnt = 0;
            int moveBlueCnt = 0;
            
            // 1. 빨간공을 움직임
            // 빨간공의 다음위치가 벽이 아니고 현위치가 구멍이 아닐때까지 반복
            while (board[nry + dy[i]][nrx + dx[i]] != BLOCK && board[nry][nrx] != HOLE) {
                nry += dy[i];
                nrx += dx[i];
                moveRedCnt++;
            }
            
            // 2. 파란공을 움직임
            // 파란공의 다음위치가 벽이 아니고 현위치가 구멍이 아닐때까지 반복
            while (board[nby + dy[i]][nbx + dx[i]] != BLOCK && board[nby][nbx] != HOLE) {
                nby += dy[i];
                nbx += dx[i];
                moveBlueCnt++;
            }
            
            // 3. 파란공이 빠진경우 제외
            if (board[nby][nbx] == HOLE) continue;
            
            // 4. 공이 겹친경우 위치를 재조정
            // 더 많이 움직인 공을 재조정
            if (nry == nby && nrx == nbx) {
                moveRedCnt > moveBlueCnt ? (nry-=dy[i], nrx-=dx[i]) : (nby-=dy[i], nbx-=dx[i]);
            }
            
            // 5. 이미 방문한 위치는 무의미하므로 제외
            if (visit[nry][nrx][nby][nbx]) continue;
            
            // 6. 판을 기울인 횟수가 10번이내일 경우 반복
            if (curBall.moveCnt < 10) {
                visit[nry][nrx][nby][nbx] = 1;
                q.push({nry, nrx, nby, nbx, curBall.moveCnt+1});
            }
            
        }
    }
    
    // 7. 불가능하거나 10번이상인 경우 -1 return
    return -1;
}
 
void solve() {
    cin>>n>>m;
    for (int y=0; y<n; y++) {
        for (int x=0; x<m; x++) {
            cin>>board[y][x];
            if (board[y][x] == RED_BALL) sry=y, srx=x;
            if (board[y][x] == BLUE_BALL) sby=y, sbx=x;
        }
    }
    
    cout<<bfs();
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    solve();
    return 0;
}