백준 13460번 구슬 탈출 2

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

삼성 기출문제이다.

구현하는게 좀 짜증나는 문제였다.

dfs + 시뮬레이션으로 풀었다.

갈수있는 경우를 깊이우선으로 탐색하여 파란 구슬을 탈출하지 않고 빨간 구슬만 탈출하는 경우, 몇번만에 탈출하였는지 벡터에 저장 후 전체탐색이 끝나면 벡터의 값 중 가장 작은 값을 출력하여주었다.

아래는 소스코드이다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
 
int m, n;
char map[10][10];
//상오하왼
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
 
vector<int> v;
 
// 정상졸료 0, 탈출 1
int move(int drt, int& ny, int& nx, int othy, int othx) {
    bool enemy = false;
    if (drt == 0) {
        //위로 이동
        if (othx == nx && othy < ny) {
            enemy = true;
        }
        for (int i = ny - 1; i > 0; i--) {
            if (enemy) {
                if (i == othy) break;
            }
            if (map[i][nx] != '.') {
                break;
            }
            ny--;
        }
        if (map[ny - 1][nx] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 1) {
        //오른쪽으로 이동
        if (othy == ny && othx > nx) {
            enemy = true;
        }
        for (int i = nx + 1; i < m - 1; i++) {
            if (enemy) {
                if (i == othx) break;
            }
            if (map[ny][i] != '.') {
                break;
            }
            nx++;
        }
        if (map[ny][nx + 1] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 2) {
        //아래로 이동
        if (othx == nx && othy > ny) {
            enemy = true;
        }
        for (int i = ny + 1; i < n - 1; i++) {
            if (enemy) {
                if (i == othy) break;
            }
            if (map[i][nx] != '.') {
                break;
            }
            ny++;
        }
        if (map[ny + 1][nx] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 3) {
        //왼쪽으로 이동
        if (othy == ny && othx < nx) {
            enemy = true;
        }
        for (int i = nx - 1; i > 0; i--) {
            if (enemy) {
                if (i == othx) break;
            }
            if (map[ny][i] != '.') {
                break;
            }
            nx--;
        }
        if (map[ny][nx - 1] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    return 3;
}
 
void go(int ry, int rx, int by, int bx, int direction, int cnt) {
    if (cnt == 10) return;
 
    for (int d = 0; d < 4; d++) {
        int wry = ry;
        int wrx = rx;
        int wby = by;
        int wbx = bx;
 
        if (direction != -1 && (direction + 2) % 4 == d) continue;
        int nry = ry + dy[d];
        int nrx = rx + dx[d];
        bool rvs = false;
        
        if (d == 0) {
            if (rx == bx && by < ry) rvs = true;
        }
        else if (d == 1) {
            if (ry == by && bx > rx) rvs = true;
        }
        else if (d == 2) {
            if (rx == bx && by > ry) rvs = true;
        }
        else if (d == 3) {
            if (ry == by && bx < rx) rvs = true;
        }
 
        if (rvs) {
            //b움직, r움직, 탈출인지 확인, 재귀
            int br = move(d, wby, wbx, wry, wrx);
            int rr = move(d, wry, wrx, wby, wbx);
            if (br == 1) continue;
            if (br == 0 && rr == 1) {
                v.push_back(cnt + 1);
                continue;
            }
            go(wry, wrx, wby, wbx, d, cnt + 1);
        }
        else {
            //r움직, b움직, 탈출인지 확인, 재귀
            int rr = move(d, wry, wrx, wby, wbx);
            int br = move(d, wby, wbx, wry, wrx);
            if (br == 1) continue;
            if (br == 0 && rr == 1) {
                v.push_back(cnt + 1);
                continue;
            }
            go(wry, wrx, wby, wbx, d, cnt + 1);
        }
    }
 
}
 
 
int main()
{
    int fRy, fRx, fBy, fBx;
    char t;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t;
            if (t == 'R') {
                fRy = i;
                fRx = j;
                map[i][j] = '.';
            }
            else if (t == 'B') {
                fBy = i;
                fBx = j;
                map[i][j] = '.';
            }
            else {
                map[i][j] = t;
            }
        }
    }
 
    go(fRy, fRx, fBy, fBx, -1, 0);
 
    if (v.size() == 0) cout << -1;
    else {
        int minr = 9999;
        for (int i = 0; i < v.size(); i++) {
            minr = min(minr, v[i]);
        }
        cout << minr;
    }
}