[SWEA 5650] 벽돌깨기

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <queue>
int T;
int N, R, C;
int board[20 + 2][20 + 2];

int block;	// 초기 블럭개수
int ans;

struct _st
{
	int x, y;
	int limit;
};
std::queue<_st> Q;

std::queue<int> GQ;
int tmp[20 + 2][20 + 2];



void input()
{
	// init
	memset(board, 0, sizeof(board));
	block = 0;
	ans = 0;

	scanf("%d %d %d", &N, &C, &R);
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			scanf("%d", &board[r][c]);
			if (board[r][c]) block++;
		}
	}
}


bool can_drop(int col)
{
	for (int r = 0; r < R; r++) {
		if (board[r][col]) return true;
	}
	return false;	// 해당 열에 맞출 벽돌이 없다
}


int drop_ball(int col)
{
	// dir
	int dir_x[4] = { 0, 0 ,1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };


	// init
	int crush = 0;
	Q = {};

	// drop ball 
	for (int r = 0; r < R; r++) {
		if (board[r][col]) {
			Q.push({ r, col, board[r][col] - 1 });
			board[r][col] = 0;	// crushed
			crush++;
			break;
		}
	}


	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();


		for (int p = 0; p < 4; p++) {
			for (int k = 0; k <= data.limit; k++) {
				int nx = data.x + dir_x[p] * k;
				int ny = data.y + dir_y[p] * k;

				if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) break;
				if (board[nx][ny] == 0) continue;
				if (board[nx][ny]) {
					Q.push({ nx, ny, board[nx][ny] - 1 });
					board[nx][ny] = 0;
					crush++;
				}
			}
		}
	}
	return crush;
}


void gravity()
{
	// init
	GQ = {};
	memset(tmp, 0, sizeof(tmp));


	for (int c = 0; c < C; c++) {
		for (int r = R - 1; r >= 0; r--) {
			if (board[r][c]) GQ.push(board[r][c]);
		}

		int row = R - 1;
		while (!GQ.empty()) {
			tmp[row][c] = GQ.front();
			GQ.pop();
			row--;
		}
	}
	memcpy(board, tmp, sizeof(tmp));
}




void DFS(int n, int cnt)
{
	if (ans < cnt) ans = cnt;
	
	if (n == N) return;

	// backup
	int bak_board[20 + 2][20 + 2] = {0, };
	memcpy(bak_board, board, sizeof(board));


	for (int c = 0; c < C; c++) {
		if (!can_drop(c)) continue;
		int res = drop_ball(c);
		gravity();
		DFS(n + 1, cnt + res);

		// undo
		memcpy(board, bak_board, sizeof(board));
	}
}




int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		input();
		DFS(0, 0);
		printf("#%d %d\n", t, block - ans);
	}
	return 0;
}

n == N일때 깬 블럭 최댓값 갱신하지 말고, 매번 갱신하다가 n == N이 될 때 DFS 함수를 리턴해준다. 

나는 블럭 깨져서 연쇄 작용 일어나는 상황을 큐로 구현했는데, DFS로 구현한 동기 코드 보니까 실행시간이 1/4이었다...ㅎ.. 최적화는 다음생에 하는걸로..