[백준 13460번] 구슬 탈출 2

문제 링크: https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

<문제 풀이> 시뮬레이션

상하좌우 기울이기 모든 조합을 다 해보면 되는데 한번 기울였을 때 RED, BLUE가 탈출에 성공했는지 여부를 저장할 bool 변수 2개가 필요하다.

 

1. 레드만 탈출 

-> 최솟값을 갱신

2. 블루가 탈출

-> 그 상태에서 4방향으로 기울이지 않고 종료한다.

 

[Left로 기울이기]

기울인 상태를 저장할 moved[10]을 준비

idx = 0 위치에 구슬을 저장할 수 있다.

각 행에 대해서 j =0  to j = M -1 모든 열을 확인한다.

만약 board[row][j]가 벽이면 idx = j + 1 위치에 구슬을 저장할 수 있다.

만약 board[row][j]가 구멍이면 idx = j 위치에 구슬을 넣어볼 수 있고, 현재 j의 위치에 구멍이 등장했다는 표시를 한다.

만약 board[row][j]가 구슬이고 idx에 구멍이 있으면 구슬을 넣는다

만약 board[row][j]가 구슬이고 idx에 구멍이 없으면 moved[idx++]에 구슬을 넣는다.

 

배열을 90도 회전하는 걸 구현하면

left 기울이기 하나만 구현해도 right, up, down을 구현할 수 있다

 

 

<C++ 소스 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int N, M;
char board[10][10];
const int INF = (1 << 30);
int res = INF;
bool left(bool &red, bool& blue) {
    for (int i = 1; i < N - 1; i++) {
        char moved[10];
        int idx = 0;
        int escapeIdx = -1;
        fill(moved, moved + 10, '.');
        for (int j = 0; j < M; j++) {
            if (board[i][j] == '#') {
                moved[j] = '#';
                idx = j + 1;
            }
            else if (board[i][j] == 'O') {                
                moved[j] = 'O';
                escapeIdx = j;
                idx = j;
            }
            else if (board[i][j] == 'R' || board[i][j] == 'B') {
                if (idx != escapeIdx) {
                    moved[idx++] = board[i][j];
                }
                else {
                    if (board[i][j] == 'R') red = true;
                    else if (board[i][j] == 'B') blue = true;
                }
                
            }
        }
        for (int j = 0; j < M; j++) {
            board[i][j] = moved[j];
        }
    }
    if (blue || red) return true;
    else return false;
}
void rotate() {
    char temp[10][10];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            temp[i][j] = board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            board[j][N - 1 -i] = temp[i][j];
        }
    }
 
    swap(N, M);
 
}
 
bool down(bool &red, bool &blue) {
    rotate();
    bool ret =left(red, blue);
    rotate();
    rotate();
    rotate();
    return ret;
}
 
bool right(bool& red, bool& blue) {
    rotate();
    rotate();
    bool ret = left(red, blue);
    rotate();
    rotate();
    return ret;
}
bool up(bool& red, bool& blue) {
    rotate();
    rotate();
    rotate();
    bool ret = left(red, blue);
    rotate();
    return ret;
}
 
void backup(char temp[10][10]) {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            board[i][j] = temp[i][j];
        }
    }
}
 
void solve(int idx) {
    if (idx == 11) return;
    char temp[10][10];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            temp[i][j] = board[i][j];
        }
    }
    bool red = false;
    bool blue = false;
    if (!left(red, blue)) {
        solve(idx + 1);
    }
    if (red && !blue) {
        res = min(res, idx);
        return;
    }
    red = false;
    blue = false;
    backup(temp);
 
    if (!up(red, blue)) {
        solve(idx + 1);
    }
    if (red && !blue) {
        res = min(res, idx);
        return;
    }
    red = false;
    blue = false;
    backup(temp);
 
    if (!right(red, blue)) {
        solve(idx + 1);
    }
    if (red && !blue) {
        res = min(res, idx);
        return;
    }
    red = false;
    blue = false;
    backup(temp);
 
    if (!down(red, blue)) {
        solve(idx + 1);
    }
    if (red && !blue) {
        res = min(res, idx);
        return;
    }
    red = false;
    blue = false;
    backup(temp);
}
 
int main(void){
    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 >> board[i][j];
        }
    }
 
    solve(1);
    if (res == INF) {
        cout << -1 << '\n';
    }
    else {
        cout << res << '\n';
    }
    return 0;
}