블록게임
문제 해석
- 게임판의 상태와 공의 발사위치가 주어졌을 때, 얻는 점수의 합을 구하는 문제입니다.
- y=0인 위치에서 왼쪽위의 45도 각도를 향한 상태로 시작합니다.
- 블록을 깨면 연결된 블록들은 모두 깨지고 점수 1을 획득합니다.
- 만약 벽에 부딪히면 반사되어 계속 진행합니다.
- y=0인 지점으로 돌아오면 종료합니다.
설계(20)
- 연결된 블록들을 부수는 것과 벽이 부딪혔을 때 반사시켜주게 구현하는게 포인트인 문제입니다.
- 먼저, 공의 발사위치가 주어지는데 0.5배의 좌표가 주어지기 때문에 double변수를 이용합니다.
- 주어지는 맵의 상태를 고려하였을 때, 주어지는 발사위치*2를 해주면 알맞은 위치에서 시작할 수 있습니다.
- 이동을 하면서, 블록을 만나면 연결된 블록들을 모두 제거하기 위해서 dfs탐색을 이용합니다.
- x.5배의 발사위치가 주어지는 경우에는 B가 나오지 않고, “l” or “-“ or “.”이 나오게 됩니다.
- “l” or “.”이 나오면 왼쪽과 오른쪽에 B가 있는지 체크한후, dfs탐색을 진행합니다.
- ”-“이 나오면 위와 아래의 상태를 체크합니다.
- 이동하면서 벽에 부딪히면 위의 벽의 경우에는 x를 반대방향으로 바꾸고, 왼쪽과 오른쪽 벽의 경우에는 y를 반대방향으로 바꾸면 됩니다.
구현(60)
코드
#include <iostream>
using namespace std;
#define MAXN 202
char map[MAXN][MAXN];
int N,M;
double K;
int dx = -1;
int dy = -1;
int dx1[] = {0,0,1,-1};
int dy1[] = {1,-1,0,0};
int dir;
int y,sy;
int ans;
void dfs(int x, int y){
for (int k = 0;k<4; k++){
int nx = x+ dx1[k];
int ny = y + dy1[k];
if (nx < 0 || ny < 0 || nx>= 2*N+1 || ny >= 2*M+1) continue;
if (map[nx][ny] == '.'){
map[nx][ny] = '|';
dfs(nx,ny);
}
else if (map[nx][ny] == 'B'){
map[nx][ny] = 'O';
dfs(nx,ny);
}
}
}
int main(){
scanf("%d%d%lf",&M,&N,&K);
y = 2*K;
sy = y;
for (int i = 0; i < 2*N+1; i++){
for (int j = 0;j < 2*M+1; j++){
scanf(" %1c",&map[i][j]);
}
}
int x = 2*N;
while (1){
x += dx;
y += dy;
if (x == 2*N) break;
if (x == 0 || y == 0 || y == 2*M) {
if (x == 0) dx*=-1;
if (y == 0 || y == 2*M) dy *= -1;
continue;
}
if (map[x][y] == 'B') {
map[x][y] = 'O';
dfs(x,y);
ans++;
}
else if (map[x][y] == '-'){
if (map[x+1][y] == 'B'){
map[x+1][y] = 'O';
dfs(x+1,y);
ans++;
}
if (map[x-1][y] =='B'){
map[x-1][y] = 'O';
dfs(x-1,y);
ans++;
}
}
else if (map[x][y] == '.' || map[x][y] == '|'){
if (map[x][y-1] == 'B'){
map[x][y-1] = 'O';
dfs(x,y-1);
ans++;
}
if (map[x][y+1] == 'B'){
map[x][y+1] = 'O';
dfs(x,y+1);
ans++;
}
}
}
printf("%d\n",ans);
return 0;
}
디버깅
- 몇가지 실수를 하였습니다.
- 벽이 반사되는 방향이 한 방향인 것으로 착각하였습니다.
- 벽의 위치에 따라서 dx와 dy를 변화시켜주는 것으로 변경하였습니다.
- map의 상태를 체크할 때, “-“인 경우를 체크하지 않았습니다.
- ”.”or”l”의 경우만으로 커버가 가능할 줄 알았는데 안되는 것 같습니다.
- 발사위치를 입력으로 받을 때, char배열을 이용하였으나, WA가 나오는거 보니 무언가 문제가 있는것 같습니다. double형으로 변경하였습니다.
제출결과
- 0ms
마무리
- 시뮬레이션 + dfs문제였습니다. 문자열 맵을 다루는데 능숙하지 않은 것 같습니다. 직접 그려가면서 정확한 좌표를 파악하였습니다.