BOJ
BOJ::4577 소코반
BOJ Gold 1
BOJ::4577 소코반
[BOJ] : https://www.acmicpc.net/problem/4577
- Level : Gold 1
시사점
- 문제 이해에만 40분을 사용하였습니다.
- 이후 로직은 명백하며, map을 a와 onlyDst로 나눠 사용하여 출력과 관리를 편하게 할 수 있었습니다.
키
- #캐릭터, #박스
이해(40)
- 입력으로 맵이 주어집니다.
- 입력으로 캐릭터의 이동방향이 주어집니다.
- 캐릭터의 이동방향에 박스가 1개있고, 해당 박스 뒤가(같은 방향) 빈 공간이라면 박스를 밀 수 있습니다.
- 캐릭터의 이동 도중 혹은 종료 후 게임이 끝났다면 complete와 맵의 상태
-
끝나지 못했다면 incomplete와 맵의 상태를 출력합니다.
- 문제를 읽고, 풀리지 않는 두 가지 의문점이 있었습니다.
- 사람 박스 박스 인 경우에 박스가 2개 다 밀리는가?
- 목표점 위에 올라간 박스도 밀리는가?
- 테스트 케이스로 밀린다/ 안밀린다 즉, 4가지 경우로 나눠놓고 테스트 해보면 되었습니다.
- 결론은, 1번은 안 밀린다 입니다.
- 2번은 밀린다 입니다.
설계, 손 코딩(10)
- 손으로 중심이 되는 코드를 구현합니다.
- 입력 받는 부분과, 시뮬레이션 하는 부분을 손으로 구현하였습니다.
- 목표점 위에 있는 박스는 밀릴 수 있기 때문에, 목표점만 있는 맵과 그 외의 것들을 가진 맵을
분리하였습니다.
- char a[MAX_N][MAX_N]; // 빈 공간, 벽, 박스 만 표시합니다. ( 캐릭터 없음 )
- bool onlyDst[MAX_N][MAX_N]; // 목표점인 경우만 true로 표시합니다.
- vector<pair<int,int> > dst; // 목표점 List를 관리하여 게임이 끝났는지 확인합니다.
시간 복잡도
공간 복잡도
손 코딩 후 문제 리뷰(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)
- MAX_NM 이 15인데, 10으로 넣고 사용하고 있었습니다.