BOJ 4577

11 Feb 2020 • ProblemSolving

소코반

문제출처

문제 해석

  • 주어진 방향키로 특정 규칙에 준수하여 이동했을 때, 목표점에 모든 박스를 올릴 수 있는지 찾는 문제입니다.
  • 특정 규칙은 다음과 같습니다.
    1. 방향키에 의해 이동할 칸이 빈칸(박스or 벽이 아닌 곳)인 경우 그 칸으로 이동합니다.
    2. 이동할 칸에 박스가 있는 경우에는 박스가 이동할 칸이 비었는지 확인한 후, 가능하면 이동시킵니다.
    3. 이동할 칸이 1)벽이거나 2)박스가 있을 때 그 다음칸도 박스가 있는경우 이동하지 않습니다.
  • 모든 박스를 목표점에 이동시킨 경우에 게임은 끝나고, 남은 방향은 무시합니다.

설계(20)

  • 주어진대로 이동만 시키면 되는 문제입니다.
  • 문제에서 나올 수 있는 문자는 7개로, 목표점 위에 있는 박스와 캐릭터도 표시가 되도록하였습니다. 그러나, 시뮬레이션 도중에는 해당 정보가 필요없기 때문에 ‘B’,’W’,’+’인 좌표들만 벡터에 저장합니다.(해당 좌표는 목표점입니다)
  • ‘B’의 경우 ‘b’로 바꿔주고, 나머지는 ‘.’로 바꿔줍니다.
  • ‘W’ 또는 ‘w’가 나올 경우, 시작 좌표 변수에 따로 저장해줍니다.
  • 각 주어진 방향에 대해서 이동할 때마다 모든 목표점에 박스가 채워지는지 확인합니다.
  • 갱신된 w의 좌표와 벡터에 저장된 목표점의 좌표에 알맞은 문자를 넣어주게 됩니다.

구현(30)

코드
#include <iostream>
#include <vector>

using namespace std;
#define MAXN 15

char map[MAXN][MAXN];

int R,C;
vector<pair<int,int> > v;
int sx,sy;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int cnt = 1;
    while (1){
        int ans = 0;
        v.clear();
        cin >> R >> C;
        if (R == 0 && C == 0) return 0;
        for (int i =0 ; i<R;i++){
            for (int j=0;j<C;j++){
                cin >> map[i][j];
                if (map[i][j] == 'W' || map[i][j] == 'w'){
                    if (map[i][j] =='W'){
                        v.push_back({i,j});
                    }
                    sx = i;
                    sy = j;
                    map[i][j] = '.';
                }
                else if (map[i][j] == 'B'){
                    v.push_back({i,j});
                    map[i][j] ='b';
                }
                else if (map[i][j] == '+'){
                    v.push_back({i,j});
                    map[i][j] = '.';
                }
            }
        }
        string order;
        cin >> order;
        int k;
        for (int i = 0 ;i < order.size(); i++){
            if (order[i] == 'U') k = 0;
            else if (order[i] == 'D') k = 1;
            else if (order[i] == 'L') k = 2;
            else k = 3;
            int nx = sx + dx[k];
            int ny = sy + dy[k];
            if (map[nx][ny] == '#') continue;
            if (map[nx][ny] == 'b'){
                int nx1 = nx + dx[k];
                int ny1 = ny + dy[k];
                if (map[nx1][ny1] == 'b' || map[nx1][ny1] == '#') continue;
                map[nx1][ny1] = 'b';
                map[nx][ny] = '.';
            }
            sx = nx;
            sy = ny;
            int sum =0;
            for (int i = 0 ;i <v.size(); i++){
                int x = v[i].first;
                int y = v[i].second;
                if (map[x][y] == 'b') sum++;
            }
            if (sum == v.size()){
                ans = sum;
                break;
            }
        }
        map[sx][sy] = 'w';
        for (int i = 0 ; i <v.size(); i++){
            int x = v[i].first;
            int y = v[i].second;
            if (map[x][y] == 'b'){
                map[x][y] = 'B';
            }
            else if (map[x][y] == 'w'){
                map[x][y] = 'W';
            }
            else map[x][y] = '+';
        }
        cout << "Game " <<cnt <<": ";
        if (ans == v.size()) cout << "complete\n";
        else cout <<"incomplete\n";
        for (int i = 0 ;i<R; i++){
            for (int j= 0;j<C;j++){
                cout << map[i][j];
            }
            cout <<"\n";
        }
        cnt++;
    }
}
디버깅
  • 주어진 문제에서 “게임이 종료되면 남은 명령은 무시한다”는 문구를 제대로 확인하지 못해서 디버깅을 통해 알게 되었습니다.
제출결과
  • 0ms

마무리

  • 특정 규칙대로 이동시키는 시뮬레이션 문제입니다. 초기에 주어진 문자만 적절히 처리해주면 어렵지 않게 구현할 수 있습니다.
 BOJ

Related Posts