SWEA5656 벽돌깨기

[SWEA 5656] 벽돌깨기

SW 벽돌깨기 문제 (로그인이 필요합니다)

시작 전

• 유명한 문제라고 해서 풀어봤는데, 진짜 생소하고 어려웠다.
• 처음에 구슬이 어디를 부숴야 최소 값이 나올지, 그리고 부숴진 벽돌에 대한 정렬을 어떻게 구현해야 할지, 그리고 벽돌이 부숴지는 연쇄작용에 대해 어떻게 풀어야 할지에 대해 감이 안왔다.(사실상, 다 몰랐던거다..)
• 처음 구현할 때는 구슬이 처음 때리는 벽돌부터 시작해서 왼쪽, 오른쪽, 아래, 위 함수를 다 구현해서 거기서 또 재귀로 해봤다가 코드도 제대로 구현하지 못함..

코드 리뷰

• 최소값은 맵크기와 구슬 던지는 횟수가 작아서 완전탐색을 재귀를 통해 구슬 던지는 횟수 N번이 다 쓰여질때마다 최소값을 저장해두는 방식으로 했다.
• 연쇄작용은 4방향을 다 보되, * K를 써서 해결했다(코드에 있음)
• 정렬 부분은 쉽다.
• 정답률에 비해 생소해서 그런지 너무 어렵게 느껴졌다.

#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 0xFFFFFF;
using namespace std;

int N, W, H;
int board[20][20];
int dc[4] = { 0,0,1,-1 };
int dr[4] = { 1,-1,0,0 };
int Min = INF;

void recur(int);
void stonesort();
void stonebreak(int, int);

void recur(int checkp) { //구슬을 던진 횟수에 대해 재귀적으로 접근
	int copy[20][20] = {};
	if (checkp == 0) { //N번만큼 구슬 던진 경우
		int cnt = 0;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (board[i][j] != 0) cnt++;
			}
		}
		Min = min(Min, cnt);
		return;
	}
	for (int i = 0; i < W; i++) { //N번만큼 아직 안 던진 경우
		int x = 0;
		while (x < H&&board[x][i] == 0) x++;
		for (int h = 0; h < H; h++) { // 재귀 돌리기 전으로 돌아가기위해 보드판 복사해놓기!
			for (int w = 0; w < W; w++) {
				copy[h][w] = board[h][w];
			}
		}
		stonebreak(x, i); //구슬 하나 써서 벽돌 깨러가는 함수
		stonesort(); // 부숴진 부분 정렬
		recur(checkp - 1); // 구슬 하나써서 재귀로 들어가기
		for (int h = 0; h < H; h++) { //보드판 복사해놓은것 가져온다.
			for (int w = 0; w < W; w++) {
				board[h][w] = copy[h][w];
			}
		}
	}
}

void stonebreak(int x, int y) {
	int score = board[x][y];
	board[x][y] = 0;
	for (int k = 0; k < score; k++) {
		for (int n = 0; n < 4; n++) {
			int xnext = x + dc[n] * k; //네방향을 보되, 그 벽돌에 들어간 점수만큼 보기위해
			int ynext = y + dr[n] * k;
			if (xnext < H&&xnext >= 0 && ynext >= 0 && ynext < W&&board[xnext][ynext] != 0) stonebreak(xnext, ynext);
		}
	}
}

void stonesort() { //벽돌 재정렬
	for (int i = 0; i < W; i++) {
		for (int j = H - 1; j > 0; j--) {
			if (board[j][i] == 0) {
				for (int k = j - 1; k >= 0; k--) {
					if (board[k][i] != 0) {
						board[j][i] = board[k][i];
						board[k][i] = 0;
						break;
					}
				}
			}
		}
	}
}
int main() {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		scanf("%d%d%d", &N, &W, &H);
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				scanf("%d", &board[i][j]);
			}
		}
		recur(N);
		printf("#%d %d\n", t, Min);
		memset(board, 0, sizeof(board));
		Min = INF;
	}
	return 0;
}