BOJ::4577 소코반

[BOJ] : https://www.acmicpc.net/problem/4577

시사점

이해(40)

설계, 손 코딩(10)

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(x)

구현(30)

함수 List

// 정답을 출력합니다.
void PRINT();

// 게임이 끝났다면 true를 return 합니다.
bool check();

// 방향을 입력받고, 게임을 진행시킵니다.
void simulate(int d);

업데이트 되는 변수

// 업데이트 되는 변수 -------------------------------------------------------------
int chx, chy; // 캐릭터의 위치를 나타냅니다.
char a[MAX_NM][MAX_NM]; // 빈공간('.'), 벽('#'), 박스('b') 만 표시합니다. ( 캐릭터 없음 )
bool onlyDst[MAX_NM][MAX_NM]; // 목표점('+')만 표시합니다.
vector<pair<int,int> > dst; // 목표지점의 목록을 관리합니다.
// 업데이트 되는 변수 -------------------------------------------------------------

실제 구현

#include<bits/stdc++.h>
const char seq[]={'U','D','L','R'};
const int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
const int MAX_NM = 15;
using namespace std;

int n, m;

// 업데이트 되는 변수 -------------------------------------------------------------
int chx, chy; // 캐릭터의 위치를 나타냅니다.
char a[MAX_NM][MAX_NM]; // 빈공간('.'), 벽('#'), 박스('b') 만 표시합니다. ( 캐릭터 없음 )
bool onlyDst[MAX_NM][MAX_NM]; // 목표점('+')만 표시합니다.
vector<pair<int,int> > dst; // 목표지점의 목록을 관리합니다.
// 업데이트 되는 변수 -------------------------------------------------------------

// 정답을 출력합니다.
void PRINT(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(onlyDst[i][j] == false){
                if(i == chx && j == chy){
                    cout << 'w';
                }else{
                    cout << a[i][j];
                }
            }else{
                if(a[i][j] == 'b'){
                    cout << 'B';
                }else if (i == chx && j == chy){
                    cout << 'W';
                }else{
                    cout << '+';
                }
            }
        }
        cout << '\n';
    }
}

// 게임이 끝났다면 true를 return 합니다.
bool check(){
    for(int i = 0; i < dst.size(); i++){
        int x = dst[i].first, y = dst[i].second;
        if(a[x][y] != 'b') return false;
    }
    return true;
}

// 방향을 입력받고, 게임을 진행시킵니다.
void simulate(int d){
    int nx = chx + dx[d], ny = chy + dy[d];
    if(a[nx][ny] == '.'){
        chx = nx, chy = ny;
    }else if(a[nx][ny] == 'b'){
        int nnx = nx + dx[d], nny = ny + dy[d];
        if(a[nnx][nny] == '.'){
            a[nnx][nny] = 'b';
            a[nx][ny] = '.';
            chx = nx, chy = ny;
        }
    }
}

int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tc = 0;
    while(true){
        dst.clear();
        tc++;
        string str = "";
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // init
                onlyDst[i][j] = false;

                cin >> a[i][j];
                if(a[i][j] == 'B'){
                    a[i][j] = 'b';
                    onlyDst[i][j] = true;
                    dst.push_back({i, j});
                }
                if(a[i][j] == 'W'){
                    onlyDst[i][j] = true;
                    dst.push_back({i, j});
                    a[i][j] = 'w';
                }
                if(a[i][j] == '+'){
                    a[i][j] = '.';
                    onlyDst[i][j] = true;
                    dst.push_back({i, j});
                }
                if(a[i][j] == 'w'){
                    chx = i, chy = j;
                    a[i][j] = '.';
                }
            }
        }
        cin >> str;
        bool ret = false;
        for(int i = 0; i < str.size(); i++){
            for(int k = 0; k < 4; k++){
                if(str[i] == seq[k]){
                    simulate(k);
                    ret = check();
                    break;
                }
            }
            if(ret == true){
                break;
            }
        }
        if(ret == true){
            cout << "Game " <<tc<< ": complete" <<'\n';
        }else{
            cout << "Game " <<tc<< ": incomplete" <<'\n';
        }
        PRINT();
    }
    return 0;
}

구현 후 코드리뷰 + 예제 돌려보기(x)

디버깅(6)

좋은 코드

최적화