BJ13460 구슬탈출2

2020.02.10

구슬탈출2

1. Solution

• Input 자료 저장 : pair로 R,B 구슬의 위치를 저장한다. 기울임 dir을 순서대로 저장하는 dirInfo 배열

• 알고리즘

  • 기본적으로 기울임 dir을 저장하는 배열에 완전탐색을 이용해서 경우의 수를 모두 저장한다.

  • 저장이 끝날 때 dirInfo 배열에 있는 방향으로 1~10 까지 기울이면서 구슬을 움직인다.

  • 이때 기울임의 방향에 따라 R,B 구슬 중 어느것이 먼저 움직여야 하는지 결정한다.

    (예를 들어 오른쪽으로 움직이도록 기울이는 경우 더 오른쪽에 있는 구슬을 먼저 움직인다.즉, x좌표가 더 큰 구슬을 먼저 움직인다.)

  • 구멍에 빠지거나 벽을 만날 때 까지 움직인다.

  • 이렇게 하게 되면 동시에 한 점에 놓일 일이 없고 만약 이 때 B 구슬이 구멍에 빠지면 실패로 끝내고 빠지지 않았을 때 R 구슬이 구멍에 빠지면 성공으로 처리해서 최소 횟수를 출력하도록 한다.

• getResult 함수 : t번부터 9번까지(10번째까지) 기울임 방향을 결정하고 기울임이 모두 결정 되었을 때 결과(최소 혹은 실패)를 가져오는 getMin 함수를 호출하는 함수. 즉, 최소 혹은 실패를 반환한다.(실패는 INF를 크게 설정해서 마지막에 main 함수에서 실패인지 확인한다.)

• getMin 함수 : dirInfo 에 차례로 넣어둔 기울임 방향에 따라 10번까지 기울임을 시도하고 이때 구슬을 움직이고 simulation 결과를 얻어오는 함수.

• getNext 함수 : 한번의 기울임을 실행하는 함수. dir에 따라 두 구슬의 x 혹은 y좌표를 비교하여 먼저 움직일 구슬을 정해서 움직이고 이때 구멍에 빠지는지 여부에 따라 리턴값을 달리한다.(1은 성공 -1은 실패 0은 둘다 멈춤)

• move 함수 : 가로/세로 중 어디로 움직이는지(XY), 어떤 구슬을 움직일지(C), 양/음 중 어느 방향으로 움직이는지(d) 를 이용해서 벽을 만나거나 구멍을 만날 때 까지 움직이는 함수. 구멍을 만나면 리턴1, 벽을 만나면 리턴0

//! 2020.02.10
// TODO BJ13460_구슬탈출2
#include <cstdio>
#include <vector>

using namespace std;
const int MAX = 15;
const int INF = 987654321;
int N,M;
int inMap[MAX][MAX];
int remMap[MAX][MAX];
pair <int,int> R;
pair <int,int> B;
int dirInfo[MAX];

void print(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            printf("%d ",inMap[i][j]);
        }
        printf("\n");
    }
}

int move(pair<int,int>& C,int XY,int d){
    inMap[C.first][C.second] = 0;
    if(XY==1){
        int nextX = C.second+d;
        while(inMap[C.first][nextX]!=1 && inMap[C.first][nextX]!=3){
            if(inMap[C.first][nextX]==2) return 1;
            nextX+=d;
        }
        C.second = nextX-d;
        inMap[C.first][C.second] = 3;
    }else{
        int nextY = C.first+d;
        while(inMap[nextY][C.second]!=1 && inMap[nextY][C.second]!=3){
            if(inMap[nextY][C.second]==2) return 1;
            nextY+=d;
        }
        C.first = nextY-d;
        inMap[C.first][C.second] = 3;
    }
    return 0;
}

int getNext(int inDir){
    int tmp1,tmp2;
    switch(inDir){
        case 0:
            if(R.second>=B.second){
                tmp1 = move(R,1,1);
                tmp2 = move(B,1,1);
                if(tmp2==1) return -1;
                else if(tmp1==1) return 1;
            }else{
                // printf("test\n");
                if(move(B,1,1)==1) return -1;
                if(move(R,1,1)==1) return 1;
            }
            break;
        case 1:
            if(R.first>=B.first){
                tmp1 = move(R,2,1);
                tmp2 = move(B,2,1);
                if(tmp2==1) return -1;
                else if(tmp1==1) return 1;
            }else{
                if(move(B,2,1)==1) return -1;
                if(move(R,2,1)==1) return 1;
            }
            break;
        case 2:
            if(R.second<=B.second){
                tmp1 = move(R,1,-1);
                tmp2 = move(B,1,-1);
                if(tmp2==1) return -1;
                else if(tmp1==1) return 1;
            }else{
                if(move(B,1,-1)==1) return -1;
                if(move(R,1,-1)==1) return 1;
            }
            break;
        case 3:
            if(R.first<=B.first){
                tmp1 = move(R,2,-1);
                tmp2 = move(B,2,-1);
                if(tmp2==1) return -1;
                else if(tmp1==1) return 1;
            }else{
                if(move(B,2,-1)==1) return -1;
                if(move(R,2,-1)==1) return 1;
            }
            break;
    }
    return 0;
}

int getMin(){
    pair <int,int> remR = R;
    pair <int,int> remB = B;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            remMap[i][j] = inMap[i][j];
        }
    }

    int result = INF;
    for(int i=0;i<10;i++){
        int ret = getNext(dirInfo[i]);
        if(ret==1){
            result = i+1;
            break;
        }
        else if(ret==-1) break;
        // print();
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            inMap[i][j] = remMap[i][j];
        }
    }
    B = remB;
    R = remR;

    return result;
}

int getResult(int t){
    int minResult = INF;
    if(t>=10){
        return getMin();
    }
    else{
        int result = 0;
        for(int dir=0;dir<4;dir++){
            dirInfo[t] = dir;
            int tmpResult = getResult(t+1);
            if(tmpResult<minResult) minResult = tmpResult;
        }
        return minResult;
    }
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++){
        char tmp[MAX];
        scanf("%s",tmp);
        for(int j=0;j<M;j++){
            if(tmp[j]=='#') inMap[i][j] = 1;
            else if(tmp[j]=='O') inMap[i][j] = 2;
            else if(tmp[j]=='R'){
                inMap[i][j] = 3;
                R = make_pair(i,j);
            }else if(tmp[j]=='B'){
                inMap[i][j] = 3;
                B = make_pair(i,j);
            }
        }
    }

    int result = getResult(0);
    if(result<=10) printf("%d\n",result);
    else printf("-1\n");

    return 0;
}

실수 : 각 함수에서 실행되는 과정을 미리 정교하게 설계하지 못해서 디버깅에 시간이 오래 걸렸고, test sample이 아닌 경우에서 어이없는 잘못된 구문들로 인해 실패했었다. 또, 완전탐색을 하는 도중에 move를 실행하게 되면 맵이 계속 바뀌어서 저장을 해줘야 하는데 이렇게 되면 시간복잡도가 O(N^10)에서 N이 4+64가 되어 대략 O(2^60)정도가 될 거라 계산했다. 이렇게 되면 시간초과가 날 가능성이 있다. 그래서 dirInfo를 완전탐색으로 경우의 수를 모두 나누고 각각의 경우에 따라 실행을 해야 했는데 이걸 잘못 짜다보니 재귀함수도 꼬였었고 정답도 나오지 않게 되었었다. 마지막으로, 문제를 잘못 이해하여 움직일 때 동시에 움직인다는 것이 한 턴에서도 먼저 B 구슬이 들어가야만 실패라고 잘못 이해하였다. 턴이 종료될 때까지 같은 턴으로 간주하여 해당 턴에서 R이 먼저들어가더라도 B도 들어가면 실패였는데 잘못 이해하여 오답을 출력했었다.

문제를 꼼꼼히 파악하고 정확히 필요한 함수들을 설계하고 구체적으로 구상해서 코딩을 하자. 그래야 오히려 차근차근 문제를 해결할 수 있다.