[BOJ-13459]째로탈출

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

[문제요약]

10번 이하로 공을 움직여서, 탈출시킬 수 있는지 확인하는 문제이다.

공은 빨간색, 파란색이 있으며 빨간색만 통과시킬 때 탈출로 인정한다.

1. 빨간색과 파란색이 동시에 탈출되는 경우는 0
2. 파란색이 먼저 탈출되는 경우도 0
3. 빨간색만 먼저 탈출되는 경우가 1

[입력]

맵의 크기

맵의 정보 

벽은 #, 빨간공은 R, 파란공은 B, 나갈수있는 구멍은 O, 빈자리는 . 로 입력된다.

[출력]

빨간색이 탈출 되는 경우가 있다면 1을 출력한다. 아니면 0 을 출력한다.

[접근방법]

DFS로 풀이할 수 있다. 각 맵은 copy를 해서 인자로 넘겨주며, 빨간공의 위치, 파란공의 위치를 넘겨준다.

그리고 총 10번의 이동 중 가능한 경우를 찾는다.

가지치기(경우의 수를 줄이기)를 위해 이전에 아래로 기울였다면, 다음 번은 아래로 기울이는 경우를 제외한 3가지 경우로 진행한다. 

공을 이동하는 경우 R을 먼저이동시키고, 이동경로에 B가 있다면 B를 모두 이동시킨 후, 다시 R을 이동시킨다.

R을 이동시키는 경우에 B가 없다면, B는 같은 경로상에 없거나, R뒤쪽에 위치한 경우므로 벽이나, R이 매칭될 때까지 이동시킨다.

이런 경우를 모두 찾고, R만이 O로 나갈 수 있다면 탈출이 되는 경우로 표시한다.

[C++11 source Code DFS+시뮬레이션]

#include<cstdio>
 
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };
const int M = 11;
 
int ROW, COL;
struct pos {
    int r, c;
};
int dfs(int tried_dir, int tried, pos red, pos blue, char mp[][M]) {
    int ret = 0;
    if (tried > 9) return ret; // 10 -> 9
 
    char nimap[M][M];
    pos nred, nblue;
    for(int i = 0 ; i < 4 ; i++){
        if (tried_dir == i) continue;
        bool red_ok = false;
        bool blue_ok = false;
        for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) nimap[r][c] = mp[r][c];
        }
        nred = red;
        nblue = blue;
        
        bool blue_is_wall = false;
        while (1) {
            int hred_r = nred.r + dr[i];
            int hred_c = nred.c + dc[i];
            if (hred_r < 0 || ROW <= hred_r || hred_c < 0 || COL <= hred_c) break;
            char next = nimap[hred_r][hred_c];
            if (next == 'O') {
                nimap[nred.r][nred.c] = '.';
                red_ok = true;
                break;
            }
            else if (next == '.') {
                nimap[hred_r][hred_c] = 'R';
                nimap[nred.r][nred.c] = '.';
                nred.r = hred_r;
                nred.c = hred_c;
            }
            else if (next == '#') break;
            else if (next == 'B') {
                if (blue_is_wall) break;
                while (1) {
                    int hblue_r = nblue.r + dr[i];
                    int hblue_c = nblue.c + dc[i];
                    if (hblue_r < 0 || ROW <= hblue_r || hblue_c < 0 || COL <= hblue_c) break;
                    int blue_next = nimap[hblue_r][hblue_c];
                    if (blue_next == 'O') {
                        nimap[nblue.r][nblue.c] = '.';
                        blue_ok = true;
                        break;
                    }
                    else if (blue_next == '.') {
                        nimap[hblue_r][hblue_c] = 'B';
                        nimap[nblue.r][nblue.c] = '.';
                        nblue.r = hblue_r; 
                        nblue.c = hblue_c;
                    }
                    else if (blue_next == '#') {
                        blue_is_wall = true;
                        break;
                    }
                }
            }
            if (blue_ok) {
                ret = 0;
                break;
            }
        } // red logic
 
        if (!blue_is_wall) {
            while (1) {
                int hblue_r = nblue.r + dr[i];
                int hblue_c = nblue.c + dc[i];
                if (hblue_r < 0 || ROW <= hblue_r || hblue_c < 0 || COL <= hblue_c) break;
                int blue_next = nimap[hblue_r][hblue_c];
                if (blue_next == 'O') {
                    blue_ok = true;
                    break;
                }
                else if (blue_next == '.') {
                    nimap[hblue_r][hblue_c] = 'B';
                    nimap[nblue.r][nblue.c] = '.';
                    nblue.r = hblue_r;
                    nblue.c = hblue_c;
                }
                else if (blue_next == '#' || blue_next == 'R') break;
            } // blue_logic
        }
 
        if (!blue_ok && !red_ok) ret = dfs(i ,tried + 1, nred, nblue, nimap);
        if (blue_ok) continue; // 멍청이
        if (red_ok || ret == 1) return ret = 1;
    }
    return ret;
}
 
int main() {
    char imap[M][M];
    scanf("%d%d", &ROW, &COL);
    pos red;
    pos blue;
    for (int r = 0; r < ROW; r++) {
        scanf("%s", imap[r]);
        for (int c = 0; c < COL; c++) {
            if (imap[r][c] == 'R') {
                red.r = r;    red.c = c;
            }
            else if (imap[r][c] == 'B') {
                blue.r = r; blue.c = c;
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < 4; i++) {
        ret = dfs(-1, 0, red, blue, imap);
        if (ret) {
            puts("1");
            break;
        }
    }
    if (!ret) puts("0");
    
    return 0;
}