4577번 소코반 문제를 풀어보았다.

4457 소코반

 

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

4577번: 소코반

 

소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다.

이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다.

다들 소코반보다는 pushpush라는 이름으로 들어본 게임일 것이다.

소코반 (acmicpc 4457번 문제)

이 게임을 클리어하는 해를 구하는 문제는 NP-Hard와 PSPACE-complete 문제에 속하여 꽤나 고난이도일 것이다.

하지만 이번 문제는 이동하는 방향을 U, D, L, R로 입력받아서 게임이 어떻게 진행되는지를 출력하는 문제이다.

게임 자체의 규칙은 간단하다.

 

1. 캐릭터에게 지시한 방향이 빈 칸(박스나 벽이 아닌 곳)인 경우에는 그 칸으로 이동한다.
2. 지시한 방향에 박스가 있는 경우에는, 박스를 민다. 이 경우에는 박스가 이동할 칸도 비어있어야 한다.
3. 지시한 방향이 벽인 경우, 또는 박스가 있는데, 박스가 이동할 칸에 다른 박스나 벽이 있는 경우에는 키를 눌러도 캐릭터는 이동하지 않는다.

모든 박스를 목표점으로 이동시킨 경우에 게임이 끝나고, 게임이 끝난 후에 입력하는 모든 키는 무시된다.

게임의 상태는 이렇게 나타낸다.

문자	뜻
.	빈 공간
#	벽
+	비어있는 목표점
b	박스
B	목표점 위에 있는 박스
w	캐릭터
W	목표점 위에 있는 캐릭터

입력은 여러 개의 테스트케이스가 주어지고, 게임의 행과 열인 R, C (4 <= R, C <= 15) 가 주어지고, R*C 만큼의 게임의 상태가 주어진다.

그리고 플레이어의 이동이 U (위), D (아래), L (왼), R (오른) 으로 주어진다.

R, C과 0 0 이 입력되면 입력이 끝난다.

예제 입력	예제 출력
8 9 ######### #. . . #. . . # #. . bb. b. # #. . . #w#. # #. . . ++++# #. . . #. . ## ######### ULRURDDDUULLDDD 6 7 ####### #. . #### #. +. +. # #. bb#w# ##. . . . # ####### DLLUDLULUURDRDDLUDRR 0 0	Game 1: incomplete ######### #. . . #. . . # #. . bb. . . # #. . . #. #. # #. . . #. #. # #. . . +W+B# #. . . #b. ## ######### Game 2: complete ####### #. . #### #. B. B. # ##. . . . # #######

 

대충 이러한 문제이다.

그래서 나는 진행 방향의 두칸 앞의 모양을 체크하고 진행하는 방식으로 풀어보았다.

 

#include <stdio.h>
#include <string.h>
#define str2UD2LR str[x+UD+UD][y+LR+LR]
#define strUDLR str[x+UD][y+LR]

int R,C,UD,LR,movlen,len,as,cnt=0;
char str[16][16], mov[51];

int UDLR(char ch) {
    if(ch=='U') {UD=-1; LR=0;}
    else if(ch=='D') {UD=1; LR=0;}
    else if(ch=='L') {UD=0; LR=-1;}
    else if(ch=='R') {UD=0; LR=1;}
}

void chk() {
    int i,j;
    as=1;
    for(i=0; i<R; i++) {
        for(j=0; j<C; j++) {
            if(str[i][j]=='b') {as=0; return;}
        }
    }
}

void wchk(int n, int m) {
    if(str[n][m]=='W') str[n][m]='+';
    if(str[n][m]=='w') str[n][m]='.';
}

void output() {
    int i,j;
    for(i=0; i<R; i++) {
        for(j=0; j<C; j++) {
            printf("%c", str[i][j]);
        }
        puts("");
    }
}

int play(int x, int y) {
    if(len==movlen) {
        chk();
        if(as) printf("Game %d: complete\n", cnt);
        else printf("Game %d: incomplete\n", cnt);
        output();
        return 0;
    }
    UDLR(mov[len]);
    chk();
    if(!as) {
        if(strUDLR=='.') {
            wchk(x,y);
            x+=UD;
            y+=LR;
            str[x][y]='w';
            len++;
            play(x,y);
        }
        else if((strUDLR=='b' || strUDLR=='B') && str2UD2LR!='b' && str2UD2LR!='B' && str2UD2LR!='#') {
            wchk(x,y);
            x+=UD;
            y+=LR;
            if(strUDLR=='+') strUDLR='B';
            else strUDLR='b';
            if(str[x][y]=='B') str[x][y]='W';
            else str[x][y]='w';
            len++;
            play(x,y);
        }
        else if(strUDLR=='+') {
            wchk(x,y);
            x+=UD;
            y+=LR;
            str[x][y]='W';
            len++;
            play(x,y);
        }
        else {len++; play(x,y);}
    }
    else {printf("Game %d: complete\n", cnt); output();}
    return 0;
}

int main()
{
    int i,j,gx,gy;
    while(1) {
        scanf("%d %d", &R, &C);
        if(!R && !C) break;
        for(i=0; i<R; i++) scanf("%s", str[i]);
        for(i=0; i<R; i++) {
            for(j=0; j<C; j++) {
                if(str[i][j]=='w' || str[i][j]=='W') {gx=i; gy=j;}
            }
        }
        scanf("%s", mov);
        movlen=strlen(mov);
        as=0;
        len=0;
        cnt++;
        play(gx, gy);
    }
    return 0;
}

 

솔직히 박스를 미는 조건문 만들 때, b와 B를 미는걸 통합시키려다가 뇌절이 많이 오기는 했다.

그리고 play함수를 한 번만 도는 상상도 못한 오류가 발생하기도 했었는데

내가 벽과 미는 공간이 없는 경우에 len을 증가시키고 play를 다시 돌리는 걸 구현하지 않았었다.

그래서 1시간동안 이상한 것만 삽질하다가 한줄 추가하고 풀려서 조금 뇌가 멈출 것 같기도 했다.

여튼 풀었다:)