[BOJ]13460번: 구슬 탈출2

생각보다 어려웠던 문제

#include <iostream>
#include <string>
#include <climits>
 
 
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
const int MAX = 20;
 
int N, M;
std::string str[MAX];
std::pair<int,int> pos_B, pos_R;
int min = INT_MAX;
int temp_Ry, temp_Rx, temp_By, temp_Bx;
 
 
void swap(int y, int x, char color) {
    char temp;
    if (str[y][x] == 'O') {
        if (color == 'R') { str[temp_Ry][temp_Rx] = '.'; }
        else if (color == 'B') { str[temp_By][temp_Bx] = '.'; }
    } else if (color == 'R') {
        temp = str[temp_Ry][temp_Rx];
        str[temp_Ry][temp_Rx] = str[y][x];
        str[y][x] = temp;
    } else if (color == 'B') {
        temp = str[temp_By][temp_Bx];
        str[temp_By][temp_Bx] = str[y][x];
        str[y][x] = temp;
    }
}
 
void moving(int y, int x, int dir, char color) {
    if (str[y][x] == '.' || str[y][x] == 'O') { return; }
 
    //해당 공이 이동할 수 있는 끝 좌표를 구한다.
    while (str[y + dy[dir]][x + dx[dir]] == '.' || str[y + dy[dir]][x + dx[dir]] == 'O') {
        y = y + dy[dir];
        x = x + dx[dir];
        if (str[y][x] == 'O') { break; }
    }신
    //구해진 좌표로 공을 이동시킨다.
    swap(y, x, color);
 
    //이동시킨 공의 좌표를 갱
    if (str[y][x] != 'O') {
        if (color == 'R') { temp_Ry = y, temp_Rx = x; }
        else if (color == 'B') { temp_By = y, temp_Bx = x; }
    }
}
 
void DFS(int count, std::pair<int, int> R, std::pair<int, int> B) {
    if (count > 10) { return; }
 
    std::string sub_plate[MAX];
    for (int i = 0; i < N; i++) { sub_plate[i] = str[i]; }
    for (int index = 0; index < 4; index++) {
        temp_Ry = R.first, temp_Rx = R.second, temp_By = B.first, temp_Bx = B.second;
 
        //공이 같은 선상으로 이동할 때 우선순위를 정하기 위한 조건문
        if ((index == 0 && R.first > B.first) || (index == 1 && R.first < B.first)
          || (index == 2 && R.second > B.second) || (index == 3 && R.second < B.second)) {
            moving(R.first, R.second, index, 'R');
            moving(B.first, B.second, index, 'B');
        } else {
            moving(B.first, B.second, index, 'B');
            moving(R.first, R.second, index, 'R');
        }
 
        //R 공을 빼냈다면 R 공은 사라지지만, B 공이 먼저 빠져나가면 안된다.(최소값을 구하기 위해 min > count 조건 사용)
        if (str[temp_Ry][temp_Rx] != 'R' && str[temp_By][temp_Bx] == 'B' && min > count) {
            min = count;
            return;
        }
 
        //기울이는 횟수를 증가시키고, R 공과, B 공의 좌표를 넣어준다.
        DFS(count + 1, { temp_Ry, temp_Rx }, { temp_By, temp_Bx });
 
        //상하좌우 방향으로 이동시키면서 기울여야하는 최소 횟수를 구하는데, 
        //moving 함수를 사용하면서 값이 변하기 때문에반복문을 돌기전 값으로 초기화
        for (int j = 0; j < N; j++) { str[j] = sub_plate[j]; }
    }
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    std::cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        std::cin >> str[i];
        for (int j = 0; j < str[i].length(); j++) {
            if (str[i][j] == 'R') {
                pos_R = {i, j};
            } else if (str[i][j] == 'B') {
                pos_B = {i, j};
            }
        }
    }
 
    DFS(1, pos_R, pos_B);
 
    if(min == INT_MAX) { min = -1; }
    std::cout << min << "\n";
    return 0;
}