SW Expert Academy - 5656. 벽돌 깨기

문제링크

• 벽돌 깨기

문제설명

• W x H 크기의 배열이 주어진다.
• 배열의 0이 아닌 칸에는 벽돌이 있으며 숫자는 벽돌이 깨졌을 때 옆으로 퍼져나가는 정도를 의미한다.
  • 벽돌은 숫자 1~9로 표현도니다.
  • 벽돌은 구슬을 맞아 깨지면 상하좌우 방향으로 (벽돌에 적힌 숫자 - 1) 만큼 옆에 있는 벽돌들도 함께 제거된다.
  • 제거되는 범위 내에 있는 벽돌은 모두 동시에 제거된다.
• N, W, H 와 벽돌의 정보가 주어질 때 N개의 구슬을 떨어뜨려 최대한 많은 벽돌을 제거하고 이때 남은 벽돌의 개수를 출력하라

문제접근

• 재귀 를 활용한 완전탐색 으로 풀었다.
• 구슬은 [0, W-1] 인덱스에 해당하는 위치에서 N번 떨어뜨릴 수 있는데, 이때 같은 자리에 중복하여 떨어뜨릴 수 있다.
• 구슬이 떨어지면서 하나의 벽돌을 깨면 연쇄효과로 주위에 있는 벽돌들이 함께 깨질 수 있는데 모든 벽돌이 동시에 깨져야 한다. 따라서, 벽돌이 깨지는 순간마다 벽돌들의 정보를 갱신하지 않고 깨질 수 있는 모든 벽돌이 깨지고 나서 벽돌 정보를 갱신해야 한다.
• 벽돌들이 깨지고 나면 빈 공간이 있는 경우 밑으로 떨어뜨린다.

구현

#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <queue>

#define MAX_N 4
#define MAX_W 12
#define MAX_H 15
#define MAX 1000
using namespace std;

typedef struct brick_info {
	int xpos;
	int ypos;
	int val;
}BrickInfo;

int N, W, H;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int board[MAX_H][MAX_W];

void breakBricks(int cidx) {
	// 깨야하는 벽돌들의 좌표
	queue<BrickInfo> cand;
	BrickInfo cBrick;
	for (int r = 0; r < H; r++) {
		if (board[r][cidx] != 0) {
			cBrick.xpos = r;
			cBrick.ypos = cidx;
			cBrick.val = board[r][cidx];
			cand.push(cBrick);
			break;
		}
	}
	if (cand.empty()) return;
	board[cBrick.xpos][cBrick.ypos] = 0;;
	// 연쇄반응
	int rboard[MAX_H][MAX_W];
	memcpy(rboard, board, sizeof(board));
	while (!cand.empty()) {
		cBrick = cand.front();
		cand.pop();
		// 현재 벽돌의 값
		int num = cBrick.val;
		board[cBrick.xpos][cBrick.ypos] = 0;
		rboard[cBrick.xpos][cBrick.ypos] = 0;
		for (int dir = 0; dir < 4; dir++) {
			int nx = cBrick.xpos;
			int ny = cBrick.ypos;
			BrickInfo nBrick;
			for (int i = 0; i < num-1; i++) {
				nx += dx[dir];
				ny += dy[dir];
				if (nx < 0 || nx >= H || ny < 0 || ny >= W) break;
				if (rboard[nx][ny] == 0) continue;
				nBrick.xpos = nx;
				nBrick.ypos = ny;
				nBrick.val = rboard[nx][ny];
				cand.push(nBrick);
				board[nx][ny] = 0;
			}
		}
	}
}

void setBricksToEmpty() {
	int updateBoard[MAX_H][MAX_W];
	memset(updateBoard, 0, sizeof(updateBoard));

	int cRow = H - 1;
	for (int c = 0; c < W; c++) {
		for (int r = H-1; r >= 0; r--) {
			if (board[r][c] != 0) {
				updateBoard[cRow--][c] = board[r][c];
			}
		}
		cRow = H - 1;
	}
	memcpy(board, updateBoard, sizeof(board));
}

int countBricks() {
	int count = 0;
	for (int r = 0; r < H; r++) {
		for (int c = 0; c < W; c++) {
			if (board[r][c] != 0) count++;
		}
	}
	return count;
}

int shootMarble(int cnt) {
	// 구슬 N번을 모두 쏜 경우
	if (cnt == N) {
		// 남아있는 벽돌의 개수를 반환
		return countBricks();
	}

	int ret = MAX;
	for (int i = 0; i < W; i++) {
		int cidx = i;
		int cboard[MAX_H][MAX_W];
		memcpy(cboard, board, sizeof(board));
		breakBricks(cidx);
		setBricksToEmpty();
		ret = min(ret, shootMarble(cnt + 1));
		memcpy(board, cboard, sizeof(cboard));
	}
	return ret;
}

int main(int argc, char** argv)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> W >> H;
		memset(board, 0, sizeof(board));
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				cin >> board[r][c];
			}
		}
		int ans = shootMarble(0);
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

구현2

#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <climits>

#define MAX_W 12
#define MAX_H 15
#define EMPTY 0

using namespace std;

int N, W, H;
int board[MAX_H][MAX_W];
int visited[MAX_H][MAX_W];
vector<int> cand;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void printBoard()
{
	printf("------------------------\n");
	for (int r = 0; r < H; r++) {
		for (int c = 0; c < W; c++) {
			printf("%d ", board[r][c]);
		}
		printf("\n");
	}
}

void init()
{
	memset(board, 0, sizeof(board));
	cand.clear();
}

void input()
{
	init();
	cin >> N >> W >> H;
	for (int r = 0; r < H; r++) {
		for (int c = 0; c < W; c++) {
			cin >> board[r][c];
		}
	}
}

void fallBlocks()
{
	int cpyBoard[MAX_H][MAX_W];
	memset(cpyBoard, 0, sizeof(cpyBoard));

	for (int c = 0; c < W; c++) {
		int nr = H - 1;
		for (int r = H - 1; r >= 0; r--) {
			if (board[r][c] == EMPTY) continue;
			cpyBoard[nr--][c] = board[r][c];
		}
	}
	memcpy(board, cpyBoard, sizeof(board));
}

void explosionChain(int sx, int sy)
{
	int length = board[sx][sy] - 1;

	for (int dir = 0; dir < 4; dir++) {
		int nx = sx;
		int ny = sy;
		for (int i = 0; i < length; i++) {
			nx += dx[dir];
			ny += dy[dir];
			if (nx < 0 || nx >= H || ny < 0 || ny >= W) break;
			if (board[nx][ny] == EMPTY) continue;
			if (visited[nx][ny]) continue;
			visited[nx][ny] = true;
			explosionChain(nx, ny);
			board[nx][ny] = 0;
		}
	}
}

void explosion(int col)
{
	int sx = -1, sy = -1;
	for (int r = 0; r < H; r++) {
		if (board[r][col] > 0) {
			sx = r;
			sy = col;
			break;
		}
	}

	if (sx == -1 && sy == -1) return;
	memset(visited, false, sizeof(visited));
	visited[sx][sy] = true;
	explosionChain(sx, sy);
	board[sx][sy] = 0;
	fallBlocks();
	// printBoard();
}

int getRemainBlocks()
{
	int ret = 0;
	for (int r = 0; r < H; r++) {
		for (int c = 0; c < W; c++) {
			if (board[r][c] == EMPTY) continue;
			ret++;
		}
	}
	return ret;
}

int explosionSelected()
{
	for (auto col : cand) {
		explosion(col);
	}

	return getRemainBlocks();
}

int playGame(int cnt)
{
	if (cnt == N) return explosionSelected();

	int ret = INT_MAX;
	for (int i = 0; i < W; i++) {
		int cboard[MAX_H][MAX_W];
		memcpy(cboard, board, sizeof(board));
		cand.push_back(i);
		ret = min(ret, playGame(cnt + 1));
		cand.pop_back();
		memcpy(board, cboard, sizeof(board));
	}
	return ret;
}

void test()
{
	input();
	cand.push_back(2);
	cand.push_back(2);
	cand.push_back(6);
	explosion(2);
	explosion(2);
	// explosion(6);
	// cout << explosionSelected() << endl;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	
	// freopen("input.txt", "r", stdin);
	cin >> T;
	// test();
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		cout << "#" << test_case << " " << playGame(0) << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}