[C++] 13460번 구슬 탈출 2 - 구현, 시뮬레이션

#include <iostream>
#include <string.h>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MA 12
#define INF 987654321

using namespace std;

int N, M;  //보드의 세로 가로 크기 N, M
char map[MA][MA];  //map
int Min;

void input()
{
    cin >> N >> M;
    LOOP(i, N) LOOP(j, M) cin >> map[i][j];
}

void f(char map[MA][MA], int cnt, int r)
{
    int flag;
    char fmap[5][MA][MA];
    
    if(cnt==10) return;  //10번 이하
    
    memset(fmap, 0, 5*MA*MA);
    LOOP(i, 4) LOOP(j, N) LOOP(k, M) fmap[i][j][k] = map[j][k];
    
    //왼쪽
    if(r!=1) { flag=0;
        LOOP(i, N) {
            for(int j=1; j<=M; j++) {
                switch(fmap[1][i][j]) {
                    case '#':
                    case '.':
                    case 'O':
                        break;
                    case 'R': {  //왼쪽으로 밀기
                        fmap[1][i][j]='.';
                        int x = j;
                        while(fmap[1][i][x-1]=='.') x--;
                        if(fmap[1][i][x-1]=='O' && !flag) flag=2;
                        else fmap[1][i][x]='R';
                        break;
                    }
                    case 'B': {
                        fmap[1][i][j]='.';
                        int x = j;
                        while(fmap[1][i][x-1]=='.' || (flag==2&&fmap[1][i][x-1]=='R')) x--;
                        if(fmap[1][i][x-1]=='O') flag=1;  //파란 공이 구멍에 들어감
                        else fmap[1][i][x]='B';
                        break;
                    }
                }
            }
        } if(flag==2 && Min>cnt) Min=cnt; if(!flag) f(fmap[1], cnt+1, 1);
    }
    //위쪽
    if(r!=2) { flag=0;
        LOOP(i, M) {
            for(int j=1; j<=N; j++) {
                switch(fmap[2][j][i]) {
                    case '#':
                    case '.':
                    case 'O':
                        break;
                    case 'R': {  //위쪽으로 밀기
                        fmap[2][j][i]='.';
                        int x = j;
                        while(fmap[2][x-1][i]=='.') x--;
                        if(fmap[2][x-1][i]=='O' && !flag) flag=2;
                        else fmap[2][x][i]='R';
                        break;
                    }
                    case 'B': {
                        fmap[2][j][i]='.';
                        int x = j;
                        while(fmap[2][x-1][i]=='.' || (flag==2&&fmap[2][x-1][i]=='R')) x--;
                        if(fmap[2][x-1][i]=='O') flag=1;  //파란 공이 구멍에 들어감
                        else fmap[2][x][i]='B';
                        break;
                    }
                }
            }
        } if(flag==2 && Min>cnt) Min=cnt; if(!flag) f(fmap[2], cnt+1, 2);
    }
    //오른쪽
    if(r!=3) { flag=0;
        LOOP(i, N) {
            for(int j=M; j>=1; j--) {
                switch(fmap[3][i][j]) {
                    case '#':
                    case '.':
                    case 'O':
                        break;
                    case 'R': {  //왼쪽으로 밀기
                        fmap[3][i][j]='.';
                        int x = j;
                        while(fmap[3][i][x+1]=='.') x++;
                        if(fmap[3][i][x+1]=='O' && !flag) flag=2;
                        else fmap[3][i][x]='R';
                        break;
                    }
                    case 'B': {
                        fmap[3][i][j]='.';
                        int x = j;
                        while(fmap[3][i][x+1]=='.' || (flag==2&&fmap[3][i][x+1]=='R')) x++;
                        if(fmap[3][i][x+1]=='O') flag=1;  //파란 공이 구멍에 들어감
                        else fmap[3][i][x]='B';
                        break;
                    }
                }
            }
        } if(flag==2 && Min>cnt) Min=cnt; if(!flag) f(fmap[3], cnt+1, 3);
    }
    //아래쪽
    if(r!=4) { flag=0;
        LOOP(i, M) {
            for(int j=N; j>=1; j--) {
                switch(fmap[4][j][i]) {
                    case '#':
                    case '.':
                    case 'O':
                        break;
                    case 'R': {  //왼쪽으로 밀기
                        fmap[4][j][i]='.';
                        int x = j;
                        while(fmap[4][x+1][i]=='.') x++;
                        if(fmap[4][x+1][i]=='O' && !flag) flag=2;
                        else fmap[4][x][i]='R';
                        break;
                    }
                    case 'B': {
                        fmap[4][j][i]='.';
                        int x = j;
                        while(fmap[4][x+1][i]=='.' || (flag==2&&fmap[4][x+1][i]=='R')) x++;
                        if(fmap[4][x+1][i]=='O') flag=1;  //파란 공이 구멍에 들어감
                        else fmap[4][x][i]='B';
                        break;
                    }
                }
            }
        } if(flag==2 && Min>cnt) Min=cnt; if(!flag) f(fmap[4], cnt+1, 4);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    Min=INF;
    f(map, 0, 0);  //맵, 횟수, 전에 기울인 방향
    
    cout << (Min==INF ? -1:Min+1);
    
    return 0;
}

엄 N*N 행렬을 계속 탐색시키면서 보드를 움직여서 시간이 24ms가 나왔다. 이거 말고 R과 B를 좌표로 설정해서 풀어낸 것도 있었다. N*N 행렬을 계속 탐색할 필요가 없고 맵도 바꿀 필요가 없어서 배열을 복사하거나 초기화할 필요가 없었다.

 

아래에 참조 링크와 그 코드의 알고리즘이 적혀있다.

 

 

<좌표로 푼 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/6910120

로그인

 

<알고리즘>

1. 입력을 받아서 R, B, O의 좌표를 알아낸다.
2. 상하좌우로 판을 기울일 것인데 기울였을 때 R이 먼저 움직일 것인지, B가 먼저 움직일 것인지를 정한다.
3. 먼저 움직이는 공을 움직이고 B가 구멍에 들어갔으면 종료, R이 구멍에 들어갔으면 후에 B가 들어갈 수 있으므로 메공이 들어갔다고 메모를 한다.
4. 기울이는 과정이 끝나고 공이 들어갔다고 메모가 되어 있을 경우 최솟값을 갱신한다.
5. 판을 기울였는데도 공의 좌표가 변하지 않았다면 더 이상 탐색할 필요가 없으므로 return
6. 상하좌우 기울인 것을 탐색한다. (기울인 방향으로 또 기울일 필요는 없다.)

 

 

<반례 모음>

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

 

 

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.