[ 백준 ] 13460 / 구슬 탈출 2

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
103/228
post-thumbnail

# Appreciation

/*
 * Problem :: 13460 / 구슬 탈출 2
 *
 * Kind :: BFS
 *
 * Insight
 * - 전체 가능한 경우의 수는 4^10번 이 아닌 2^10번 이다
 *   + 방금 전 기울인 쪽으로 보드를 다시 기울이는 것은 아무 의미가 없다
 *   + 방금 전 기울인 쪽의 반대 방향으로 보드를 기울이는 것은 아무 의미가 없다
 *
 * Point
 * - 각각의 구슬이 한 칸씩 이동할 때마다, 구멍에 빠졌는지 그렇지 않은지 확인해주어야 한다
 *   # 한칸 한칸 움직일 때마다 구슬을 추적해야 한다
 *
 * - 보드를 기울인 후, 구슬의 상태에 따라 추후 게임의 진행여부가 결정된다
 *   # 편의상 보드를 기울이는 것을 구현한 함수에서 상태를 표시하는 값을 같이 반환하여 구현했다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, M;
char board[10][10];
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};
struct Point { int y, x; };
struct Status { int pd; Point R, B; };
Point O;
#define SUCCESS  1
#define CONTINUE 0
#define FAIL    -1

// Set up : Functions Declaration
bool operator == (const Point &u, const Point &v);
pair<int,Status> tilt(Status C, int dir);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    Point SR{}, SB{}; /* 빨간 구슬 시작위치, 파란 구슬 시작위치 */
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        string line; cin >> line;
        for (int j=0; j<M; j++) {
            board[i][j] = line.at(j);
            if (board[i][j] != '#') {
                if (board[i][j] == 'R') {
                    SR.y = i; SR.x = j;
                }
                if (board[i][j] == 'B') {
                    SB.y = i; SB.x = j;
                }
                if (board[i][j] == 'O') {
                    O.y = i; O.x = j;
                }
                board[i][j] = '.'; /* board 에는 '.' 과 '#' 만 남게됨 */
            }
        }
    }

    // Process
    queue<Status> que;
    /* 게임 중간의 상태는 이전에 보드를 기울였던 방향과 각 구슬의 위치로 나타낼 수 있음 */
    que.push({-1, SR, SB}); /* 초기 상태를 Queue 에 넣어줌 */

    int cnt = 0; /* 보드를 기울인 횟수 */
    while (not(que.empty())) {
        int size = que.size();
        cnt++;
        if (cnt > 10) break; /* 10번 넘게 보드를 기울이는 경우는 고려하지 않음 */
        while (size--) {
            Status C = que.front(); /* 현재 다루고 있는 게임 중간 상태 */
            int pd = C.pd; /* previous direction */
            que.pop();

            for (int i=0; i<4; i++) {
                /* 이전에 기울였던 방향, 또는 그 반대 방향이면 그냥 넘어감 */
                if (pd == i || 3-pd == i) continue;
                int code; Status A{};
                /* 보드를 i 방향으로 기울여서
                 * 게임의 결과를 나타내는 code 와 상태를 나타내는 Status 를 받음 */
                tie(code, A) = tilt(C, i);

                // Control : Output
                /* 성공 */
                if (code == SUCCESS) {
                    cout << cnt << endl;
                    exit(0);
                }
                /* 게임 계속 */
                else if (code == CONTINUE) {
                    que.push(A);
                }
                /* 실패는 그대로 게임종료 */
            }
        }
    }

    // Control : Output
    cout << -1 << endl;
}

// Helper Functions
bool operator == (const Point &u, const Point &v)
/* 좌표 비교를 편하게 하기 위해서 연산자 오버로딩을 함 */
{
    return make_tuple(u.x, u.y) == make_tuple(v.x, v.y);
}

pair<int,Status> tilt(Status C, int dir)
/* 보드를 dir 방향으로 기울인 후, 게임의 결과를 나타내는 (int)code 와 게임의 상태를 반환함 */
{
    Point CR = C.R; /* 현재 빨간 구슬의 위치 */
    Point CB = C.B; /* 현재 파란 구슬의 위치 */

    bool isRMoved, isBMoved;
    bool isRFallen = false, isBFallen = false;

    do {
        isRMoved = false;
        isBMoved = false;

        if (not(isRFallen)) { /* 현재 빨간 구슬이 떨어지지 않았다면 */
            int nry = CR.y + dy[dir]; /* new R y */
            int nrx = CR.x + dx[dir]; /* new R x */
            Point NR{nry, nrx};
            /* 다음 빨간 구슬의 위치가 장애물이 아니고 */
            if (board[nry][nrx] != '#') {
                /* 구멍이거나 현재 파란구슬이 있는 위치가 아니라면 */
                if (NR == O || not(NR == CB)) {
                    /* 움직인다 */
                    isRMoved = true;
                    /* 빨간 구슬의 위치 갱신 */
                    CR = NR;
                }
            }
        }
        if (not(isBFallen)) { /* 현재 파란 구슬이 떨어지지 않았다면 */
            int nby = CB.y + dy[dir]; /* new B y */
            int nbx = CB.x + dx[dir]; /* new B x */
            Point NB{nby, nbx};
            /* 당음 파란 구슬의 위치가 장애물이 아니고 */
            if (board[nby][nbx] != '#') {
                /* 구멍이거나 현재 파란구슬이 있는 위치가 아니라면 */
                if (NB == O || not(NB == CR)) {
                    /* 움직인다 */
                    isBMoved = true;
                    /* 파란 구슬의 위치 갱신 */
                    CB = NB;
                }
            }
        }

        /* 각각의 구슬이 떨어졌는지 확인 */
        isRFallen = (CR == O);
        isBFallen = (CB == O);
    } while (isRMoved || isBMoved); /* 두 구슬이 모두 움직이지 않을 때까지 반복 */

    /* 파란 구슬이 떨어졌으면 */
    if (isBFallen) {
        /* 실패 */
        return {FAIL, {dir, CR, CB}};
    /* 파란 구슬은 안 떨어졌는데 */
    /* 빨간 구슬이 떨어졌으면 */
    } else if (isRFallen) {
        /* 성공 */
        return {SUCCESS, {dir, CR, CB}};
    /* 빨간 구슬도 안 떨어졌으면 */
    } else {
        /* 게임 계속 */
        return {CONTINUE, {dir, CR, CB}};
    }
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글