13460 구슬 탈출 2

삼성 SW 역량 문제.

 

방향이 4방향이니까,

한 방향에 대해서 깊히 생각해보고 구현하면 나머지는 비슷한 방법이다.

그래서 코드도 비슷하지만, 길어진 코드가 되었다.

 

 

총평
    - 모든 경우의 수를 세는 dfs는 잘 구현했다.
    - dfs 기저조건에서, 최솟값을 구하는 방법을 이제는 낯설어 하지 말자.
    - 결국, 시뮬레이션의 디테일한 구성사항을 논리적 오류없이 구현해야하는 것이 중요했다.
    - 반례들을 몇 십 차례 적용해 본 결과로 논리적 허점을 찾고, 수정하여 답을 얻었다.
    - 문제였던 곳은, 빨간공과 파란공이 같은 선 상에 있을 때, 움직인 후 겹치지 않게 처리하는 부분이었다.
        이 부분을 알고리즘 처음 짤 때부터, 신중히 생각하고 만들었으면, 더 좋았을 것 같다.

#include <cstdio>

int N, M;
char a[10][10];
int order[10];
const int max_cnt = 10;
const int INF = 11;
int ans = INF;

struct Ball{
    int x, y;
};
Ball red, blue;
Ball ori_red, ori_blue;
bool red_goal, blue_goal;

void printOrder(){
    for (int i=0; i<max_cnt; ++i){
        printf("%d ", order[i]);
    }
    puts("");
}

int get_minimum_tilt_count(){
    red.x = ori_red.x; red.y = ori_red.y;
    blue.x = ori_blue.x; blue.y = ori_blue.y;
    red_goal = false; blue_goal = false;
    for (int step=0; step<max_cnt; ++step){
        // up
        if (order[step] == 0){
            bool blueFirst = false, sameline = false;
            if (blue.y == red.y) {
                sameline = true;
                if (blue.x > red.x) blueFirst = true; 
            }
            // blue
            int col = blue.y;
            for (int i=blue.x - 1; i>=0; --i){
                if (a[i][col] == '#') {blue.x = i + 1; break;}
                else if (a[i][col] == 'O') {blue_goal = true; break;}
            }
            // red
            col = red.y;
            for (int i=red.x - 1; i>=0; --i){
                if (a[i][col] == '#') {red.x = i + 1; break;}
                else if (a[i][col] == 'O') {red_goal = true; break;}
            }
            if (blue.x == red.x && sameline){
                if (blueFirst) ++blue.x;
                else ++red.x;
            }
        }
        // down
        else if (order[step] == 1){
            bool blueFirst = false, sameline = false;
            if (blue.y == red.y){
                sameline = true;
                if (blue.x > red.x) blueFirst = true; 
            }
            // blue
            int col = blue.y;
            for (int i=blue.x + 1; i<N; ++i){
                if (a[i][col] == '#') {blue.x = i - 1; break;}
                else if (a[i][col] == 'O') {blue_goal = true; break;}
            }
            // red
            col = red.y;
            for (int i=red.x + 1; i<N; ++i){
                if (a[i][col] == '#') {red.x = i - 1; break;}
                else if (a[i][col] == 'O') {red_goal = true; break;}
            }
            if (blue.x == red.x && sameline){
                if (blueFirst) --red.x;
                else --blue.x;
            } 
        }
        // left
        else if (order[step] == 2){
            bool blueFirst = false, sameline = false;
            if (blue.x == red.x) {
                sameline = true;
                if (blue.y > red.y) blueFirst = true;
            }
            // blue
            int row = blue.x;
            for (int j=blue.y - 1; j>=0; --j){
                if (a[row][j] == '#') {blue.y = j + 1; break;}
                else if (a[row][j] == 'O') {blue_goal = true; break;}
            }
            // red
            row = red.x;
            for (int j=red.y - 1; j>=0; --j){
                if (a[row][j] == '#') {red.y = j + 1; break;}
                else if (a[row][j] == 'O') {red_goal = true; break;}
            }
            if (blue.y == red.y && sameline) {
                if (blueFirst) ++blue.y;
                else ++red.y;
            } 
        }
        // right
        else if (order[step] == 3) {
            bool blueFirst = false, sameline = false;
            if (blue.x == red.x) {
                sameline = true;
                if (blue.y > red.y) blueFirst = true;
            }
            // blue
            int row = blue.x;
            for (int j=blue.y + 1; j<M; ++j){
                if (a[row][j] == '#') {blue.y = j - 1; break;}
                else if (a[row][j] == 'O') {blue_goal = true; break;}
            }
            // red
            row = red.x;
            for (int j=red.y + 1; j<M; ++j){
                if (a[row][j] == '#') {red.y = j - 1; break;}
                else if (a[row][j] == 'O') {red_goal = true; break;}
            }
            if (blue.y == red.y && sameline) {
                if (blueFirst) --red.y;
                else --blue.y;
            }
        }

        if (blue_goal) { 
            return INF;
        }
        else if (red_goal) {
            return step + 1;
        }
    }
    return INF;
}

void dfs(int depth){
    if (depth == max_cnt){
        int min_step = get_minimum_tilt_count();
        // printOrder();
        // printf("ans(%d)\n", ans);
        if (ans > min_step ) ans = min_step;
        return;
    }
    for (int i=0; i<4; ++i){
        if (order[depth - 1] != i){
            order[depth] = i;
            dfs(depth + 1);
        }
    }
}

void gameStart(){
    for (int i=0; i<4; ++i){
        order[0] = i;
        dfs(1);
    }
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i=0; i<N; ++i){
        char str[12];
        scanf("%s", str);
        for (int j=0; j<M; ++j){
            a[i][j] = str[j];
            if (a[i][j] == 'R'){
                ori_red.x = i; ori_red.y = j; a[i][j] = '.';
            }
            else if (a[i][j] == 'B'){
                ori_blue.x = i; ori_blue.y = j; a[i][j] = '.';
            }
        }
    }
    gameStart();
    if (ans == INF) puts("-1");
    else printf("%d\n", ans);
    return 0;
}