SWEA5656

22 Jan 2020 • ProblemSolving

벽돌 깨기

문제출처

1.설계(23분)

  • 문제 해석

    • 구슬을 쏘아 벽돌을 깨트리는 게임.
    • WxH배열에 위에서 아래로 N번 구슬을 쏜다. Arr[i] = 0 이면 빈 공간, 나머지 숫자는 벽돌을 의미한다.
    • 구슬은 항상 맨 위에 있는 벽돌만 깨트린다.
    • 구슬에 명중한 벽돌은 상하좌우로 (벽돌의 숫자 - 1) 칸 제거된다.
    • 제거되는 범위 내의 벽돌은 동시에 제거된다.
    • 빈 공간이 있을 경우 벽돌은 밑으로 떨어진다.
    • 1 <= N <= 4, 2 <= W <= 12, 2 <= H <= 12

  • 설계

    • 첫번째로 어느 위치에 구슬을 떨어트릴 지 선정, 완전탐색으로 지정한다.

    • 두번째로 지정된 위치에서 구슬을 떨어트린 후, 벽돌을 깬다.

      Bomb(벽돌의 숫자 -1 , x , y) 함수를 이용하여 재귀적으로 터트리도록 하였다. 탐색이 중복되는 부분이 많아서 이를 최적화 해보려 했으나 다른 방법을 찾지 못하였다.

    • 세번째로 구슬을 떨어트릴 때마다, 붕 떠있는 벽돌들을 아래로 내려준다. 이는 단순 반복문으로 처리 가능하였다.

2.구현(40분)

  • 코드
#include <iostream>
#include <cstring>
#define MAXN 4
#define MAXW 12
#define MAXH 15
#define INF 987654321
using namespace std;

int arr[MAXH][MAXW];
int copy_arr[MAXH][MAXW];
int num[MAXN];
int N, W, H;
int ans;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
void Bomb(int cnt, int x, int y) {
	
	copy_arr[x][y] = 0;
	

	if (cnt > 0) {
		for (int k = 0; k < 4; k++) {
			int nx = x;
			int ny = y;
			int tmp_cnt = 0;
			while (tmp_cnt < cnt) {
				nx += dx[k];
				ny += dy[k];
				if (nx < 0 || ny < 0 || nx >= H || ny >= W) break;
				if (copy_arr[nx][ny]) {
					Bomb(copy_arr[nx][ny] - 1, nx, ny);
				}
				tmp_cnt++;
			}
		}
	}
}
void Drop() {
	for (int j = 0; j < W; j++) {
		int idx = 0;
		for (int i = H - 1; i >= 0; i--) {
			if (copy_arr[i][j]) {
				copy_arr[H - 1 - idx][j] = copy_arr[i][j];
				if (H - 1 - idx != i) copy_arr[i][j] = 0;
				idx++;
			}
		}
	}
}
void dfs(int cnt) {
	if (ans == 0) return;
	if (cnt == N) {
		memcpy(copy_arr, arr, sizeof(arr));
		
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < H; j++) {
				if (copy_arr[j][num[i]]) {
		
					Bomb(copy_arr[j][num[i]]-1, j, num[i]);
					
					Drop();
					break;
				}
			}
		}
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (copy_arr[i][j]) sum++;
			}
		}
		if (ans > sum) ans = sum;
		return;
	}
	for (int i = 0; i < W; i++) {
		num[cnt] = i;
		dfs(cnt + 1);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	for (int test_case = 1; test_case <= t; test_case++) {
		ans = INF;
		cin >> N >> W >> H;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				cin >> arr[i][j];
			}
		}
		dfs(0);
		cout << "#"<< test_case<<" "<< ans << "\n";
	}
	return 0;
}

  • 디버깅

    디버깅하는데에 시간을 아주 많이 썼다. 벽돌을 깨트리는 함수 구현에서 tmp_arr 배열을 따로 구성하여 copy_arr배열의 조건을 보고 tmp_arr배열의 벽돌을 지우는 실수를 하였다. 이를 깨닫는 데 시간이 조금 걸렸다. 또한, 범위를 벗어날 시 break를 걸어주는 것을 continue로 잘못 구현하였다. Drop함수를 구현할 때에도 주먹구구식으로 3중 for문을 작성하였고, 이를 2중 for문으로 줄이는데에 시간이 걸렸다.

  • 제출결과

    104ms

3.마무리

  • 해당 문제는 단순히 하라는데로 구현만 하면 되는 문제이다. 그러나 시간을 1시간정도 써버렸고, 설계할 때에 어떤 함수를 쓰겠다고 지정하고 함수의 내부적 구조를 깊게 생각 안한 상태에서 코딩에 들어갔기 때문에 디버깅에 시간을 많이 써버렸다. 구현하기 전에 pseudo코드를 어느정도 수기로 작성해보고 코딩하는 습관을 길들여야 할 것 같다.
 SWEA

Related Posts