본문 바로가기
Algorithm/삼성 SW 역량 테스트 기출 문제

[Baekjoon][13460] 구슬 탈출 2

by 어발 2022. 1. 12.

출처 - 백준사이트

13460번: 구슬 탈출 2

해설 및 주석은 나중에 업로드 예정

#include <iostream>
#include <cstring>

#define MAX        11

using namespace std;

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

char map[MAX][MAX] = {0, };
int N, M;
int result = 11;
bool isOut = false, isBout = false, isRout = false;

void moving(int dir) {
    pair<int, int> Blue, Red, tBlue, tRed;
    bool isBstop = false, isRstop = false, isRB = false, isBR = false;
    isBout = false, isRout = false;

    for (int y=0 ; y<N ; y++) {
        for (int x=0 ; x<M ; x++) {
            if (map[y][x] == 'R')
                Red.first = y, Red.second = x;
            else if (map[y][x] == 'B')
                Blue.first = y, Blue.second = x;
        }
    }

    while (!(isBstop && isRstop)) {
        tBlue = Blue, tRed = Red;

        if (!isBout) {
            if (map[Blue.first + dy[dir]][Blue.second + dx[dir]] == '.') {
                map[Blue.first][Blue.second] = '.';
                Blue.first += dy[dir];
                Blue.second += dx[dir];
                map[Blue.first][Blue.second] = 'B';
            }
            else if (map[Blue.first + dy[dir]][Blue.second + dx[dir]] == 'O') {
                map[Blue.first][Blue.second] = '.';
                Blue.first += dy[dir];
                Blue.second += dx[dir];
                map[Blue.first][Blue.second] = 'O';
                isBout = true;            
            }
        }

        if (!isRout) {
            if (map[Red.first + dy[dir]][Red.second + dx[dir]] == '.') {
                map[Red.first][Red.second] = '.';
                Red.first += dy[dir];
                Red.second += dx[dir];
                map[Red.first][Red.second] = 'R';
            }
            else if (map[Red.first + dy[dir]][Red.second + dx[dir]] == 'O') {
                map[Red.first][Red.second] = '.';
                Red.first += dy[dir];
                Red.second += dx[dir];
                map[Red.first][Red.second] = 'O';
                isRout = true;
            }
        }

        if (Blue == tBlue)
            isBstop = true;
        else
            isBstop = false;

        if (Red == tRed)
            isRstop = true;
        else
            isRstop = false;
    }

    if (isRout && !isBout)
        isOut = true;

    return;
}

void getResult(int count, int prev_dir) {
    if (count == 11)
        return;    

    for (int i=0 ; i<4 ; i++) {
        char tempmap[MAX][MAX] = {0, };

        if (prev_dir == i)
            continue;

        memcpy(tempmap, map, sizeof(map));
        count++;
        moving(i);

        if (isOut == true) {
            if (count < result)
                result = count;

            isOut = false;
            return;
        }
        else {
            if (!isRout && !isBout)
                getResult(count, i);
        }

        memcpy(map, tempmap, sizeof(map));
        count--;
    }
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M;

    for (int y=0 ; y<N ; y++)
        cin >> map[y];

    getResult(0, -1);

    if (result == 11)
        cout << -1;
    else
        cout << result;

    return 0;
}
728x90

댓글