백준 13460 / 구슬 탈출 2 (해결)

캐도캐도 끝없이 반례가 나온다.

정신나간다.

내 코드는 500줄 가까이되도 정답이 아닌데

다른 정답코드를 보니 100줄만 되도 맞더라.

다음에 다시 꼭 풀어볼문제.

코드가 굉장히 더럽다.

반례

https://www.acmicpc.net/board/view/23382

풀었다.

해답은 '10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.' 에 있다.

판을 기울이는 모든 경우에 대해 생각해보자.

일단 첫번째, 오,왼,위,아래로 기울일 수 있다.

그다음 두번째도 물론 오왼위아래로 기울일 수 있지만, 잘 생각해보면

오오, 왼왼, 위위, 아래아래가 의미가 없다. 

또한

오왼, 왼오, 위아래, 아래위는 구슬의 위치가 다시 돌아옴으로 이것또한 의미가 없다.

그렇다면

오아래, 왼아래, 왼위, 오위 같은 기울임에 의미가 있는 것들만 따져보자.

첫 기울임은 오윈위아래 4가지가 가능하고

두번째는 첫번째 방향과 같은 경우와 첫번째 방향과 반대 경우만 아니면 된다.

그러므로 경우의 수는

4*2*2*..........*2이다.

10번 기울일 수 있다는 조건때문에, 4*2^9 = 2048번의 경우의수가 가능하다.

위의 조건에 맞는 경우의수들을 오 0, 왼 1, 아래 2, 위 3 와 같이 숫자로 표현한 다음 크기 10짜리 벡터안에 넣고

완성된 2048개의 벡터에 따라 맵을 기울여보면 된다.

또 맵을 기울일시, 파란 공을 먼저 움직이느냐, 빨간 공을 먼저 움직이느냐 결정하는 것도 중요하다. 

(빨)(파)(벽)의 경우 빨간색이 먼저 움직이지 않을 시 파란색은 움직일 수 없기 떄문.

여러가지 상황들을 고려하여 체크하는 방법이 있겠지만 

나는 그냥 한 방향에 대해 2번씩 기울였다. 빨간색 한번 파란색 한번 그다음 빨간색 한번 파란색 한번.

이렇게하면 무엇을 먼저 움직이는 지 고려하지 않아도 된다.

중간에 파란색이 구멍에 안빠졌는데 빨간색이 구멍에 빠진 경우를 찾으면 횟수를 최소값과 비교한다.

답을 찾지 못했다면 -1을 출력.

굉장히 어려운 문제였다. 그냥 구현한다면 글 맨 위 처럼 수많은 반례들이 존재하기 때문.

역시나 이 문제도 문제를 해결하는 아이디어가 중요함을 다시금 깨닫게 해줬다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
 
int n, m;
vector<vector<char>>map(10,vector<char>(10,'a'));
vector<vector<char>>orimap(10, vector<char>(10, 'a'));
 
int dx[] = {0,0,1,-1 }; 
int dy[] = { 1,-1,0,0 };
 
vector<int>dir;
 
bool redin = false;
bool bluein = false;
 
int ans = 11;
 
void move(int x, int y, int wdir, char color) {
 
    bool canmove = true;
    int st = 0;
 
    while (canmove) {
        st++;
        int nx = x + st * dx[wdir];
        int ny = y + st * dy[wdir];
 
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            if (map[nx][ny] != '.') {
                if (map[nx][ny] == 'O') {
                    if (color == 'R') {
                        map[x][y] = '.';
                        redin = true;
                    }
                    if (color == 'B') {
                        map[x][y] = '.';
                        bluein = true;
                    }
                    break;
                }
                else {
                    map[x][y] = '.';
                    map[nx - dx[wdir]][ny - dy[wdir]] = color;
                    break;
                }
            }
        }
    }
    return;
 
}
void doit(vector<int>dir, int cnt) {
 
    int rx, ry, bx, by;
 
    if (bluein == false) {
        if (redin == true) {
            if (ans > cnt) {
                ans = cnt;
                return;
            }
        }
    }
 
    if (cnt == 10) {
        return;
    }
 
    for (int k = 0; k < 2; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'R') {
                    rx = i; ry = j;
                    move(rx, ry, dir[cnt], 'R');
                }
                if (map[i][j] == 'B') {
                    bx = i, by = j;
                    move(bx, by, dir[cnt], 'B');
                }
            }
        }
    }
 
    doit(dir, cnt + 1);
}
void makedir(int idx, int pr) { // 동 1, 서 2, 남 3, 북 4
    if (idx == 10) {
        bluein = false, redin = false;
 
        for(int i=0;i<n;i++){
            for (int j = 0; j < m; j++) {
                map[i][j] = orimap[i][j];
            }
        }
 
        doit(dir, 0);
        return;
    }
 
    if (pr == -1) {
        for (int i = 0; i < 4; i++) {
            dir[idx] = i;
            makedir(1, i);
        }
    }
 
    if (pr == 0 || pr == 1) {
        dir[idx] = 2;
        makedir(idx + 1, 2);
        dir[idx] = 3;
        makedir(idx + 1, 3);
    }
    if (pr == 2 || pr == 3) {
        dir[idx] = 0;
        makedir(idx + 1, 0);
        dir[idx] = 1;
        makedir(idx + 1, 1);
    }
}
 
int main() {
    //freopen("Text.txt", "r", stdin);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> orimap[i][j];
        }
    }
 
    dir.resize(10);
    
    makedir(0, -1);
    
    if (ans != 11) {
        cout << ans;
    }
    else {
        cout << -1;
    }
}