[C++] 백준 13460 - 구슬 탈출2

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

13460번: 구슬 탈출 2

<풀이>

1. 보드 상태를 입력받는다.

2. 빨간 구슬을 뺄 수 있는 최소 움직임을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 경우를 다 해보지 않고서는 풀 수 없습니다. 저는 문제를 읽고 모든 경우를 다 해보는 브루트포스를 선택하였습니다.

 

2. 중복된 탐색 줄이기

=> 모든 경우를 다 해볼경우 중복된 경우가 많이 나올 수 있습니다. 예를 들어, 오른쪽 왼쪽을 반복하는 경우가 있습니다. 저는 중복된 경우를 줄이기 위해서, 빨간공과 파란공의 좌표의 조합으로 방문배열(visited[redX][redY][blueX][blueY])을 반들었습니다. 이렇게 하면 전에 탐색했던 빨간공과 파란공 좌표는 탐색하지 않으므로 중복을 줄일 수 있습니다.

 

3. 구슬 굴리는 방법

=> 각자 구슬을 신경쓰지 않고 일단 굴립니다. 이 때 겹쳐질 수도 있습니다. 이 후 두 구슬이 같은 곳에 있다면, 움직인 거리에 따라서 구슬의 위치를 정렬합니다. 

 

#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, M;
char map[10][10];
bool visited[10][10][10][10];
int rX, rY, bX, bY;
int answer;
 
bool isExit(int x, int y) {
    if (map[x][y] == 'O') return true;
    return false;
}
 
bool isSamePosition(int x1, int y1, int x2, int y2) {
    if (x1 == x2 && y1 == y2) return true;
    return false;
}
 
void roll(int& x, int& y, int& dir, int& distance, bool& exit) {
    while (map[x+dx[dir]][y+dy[dir]] != '#') {
        x += dx[dir];
        y += dy[dir];
        distance++;
        if (map[x][y] == 'O') {
            exit = true;
            break;
        }
    }
}
 
int simulation(int rx, int ry, int bx, int by, int cnt) {
 
    if (cnt > 10) return INF;
 
    if (isExit(rx, ry) || isExit(bx, by)) {
        if (isExit(bx, by)) return INF;
        return 0;
    }
 
    int ret = INF;
 
    for (int i = 0; i < 4; i++) {
        int nrx = rx, nry = ry, nbx = bx, nby = by;
        int rd = 0, bd = 0;
        bool re = false, be = false;
 
        roll(nrx, nry, i, rd, re);
        roll(nbx, nby, i, bd, be);
 
        //둘 중 하나라도 탈출한 경우
        if (re || be) {
            ret = min(ret, simulation(nrx, nry, nbx, nby, cnt + 1) + 1);
        }
        else {
            //구슬 순서 정리
            if (isSamePosition(nrx, nry, nbx, nby)) {
                if (rd > bd) nrx -= dx[i], nry -= dy[i];
                else nbx -= dx[i], nby -= dy[i];
            }
 
            if (!visited[nrx][nry][nbx][nby]) {
                visited[nrx][nry][nbx][nby] = true;
                ret = min(ret, simulation(nrx, nry, nbx, nby, cnt + 1) + 1);
                visited[nrx][nry][nbx][nby] = false;
            }
        }
    }
 
    return ret;
}
 
void solution() {
    visited[rX][rY][bX][bY] = true;
    answer = simulation(rX, rY, bX, bY, 0);
    visited[rX][rY][bX][bY] = false;
    answer = (answer == INF) ? -1 : answer;
}
 
int main() {
    //초기화
    N = 0, M = 0;
    memset(map, '0', sizeof(map));
    memset(visited, false, sizeof(visited));
    rX = 0, rY = 0, bX = 0, bY = 0;
    answer = 0;
 
    //입력
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') {
                map[i][j] = '.';
                rX = i, rY = j;
            }
            else if (map[i][j] == 'B') {
                map[i][j] = '.';
                bX = i, bY = j;
            }
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 구현에 대해 알아볼 수 있는 문제였습니다.