5656. [모의 SW 역량테스트] 벽돌 깨기

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int n,h, w;
int map[15][12];
int mapc[15][12];
int tc;
int result = 1000000;

struct brick {
	int x; int y;
	int value;
	brick(int a, int b, int c) {
		x = a; y = b; value = c;
	}
};
void sorting() {
	for (int i = 0; i < w; i++) {
		for (int j = h - 1; j >= 0; j--) {
			if (map[j][i] == 0) {
				for (int k = j - 1; k >= 0; k--) {
					if (map[k][i] != 0) {
						map[j][i] = map[k][i];
						map[k][i] = 0;
						break;
					}
				}
			}
		}
	}
}

void crush(brick bric) {
	queue<brick> q;
	int xx = bric.x; int yy = bric.y; int v = bric.value;
	brick nextbrick(xx, yy, v);
	if (v == 1) {
		map[xx][yy] = 0;
		sorting();
		return;
	}
	q.push(brick(xx, yy, v));
	
	while (!q.empty()) {
		xx = q.front().x; yy = q.front().y; v = q.front().value;
		q.pop();
		for (int i = xx; i < xx + v; i++) {
			if (i < h) {
				if (i != xx && map[i][yy] > 1) {
					q.push(brick(i, yy, map[i][yy]));
				}
				map[i][yy] = 0;
			}		
		}
		
		for (int i = xx; i > xx - v; i--) {
			if (i >= 0) {
				if (i != xx && map[i][yy] > 1) {
					q.push(brick(i, yy, map[i][yy]));
				}
				map[i][yy] = 0;
			}
		}
		
		
		for (int i = yy; i < yy + v; i++) {
			if (i < w) {
				if (i != yy && map[xx][i] > 1) {
					q.push(brick(xx, i, map[xx][i]));
				}
				map[xx][i] = 0;
			}
		}
		
		
		for (int i = yy; i > yy - v; i--) {
			if (i >= 0) {
				if (i != yy && map[xx][i] > 1) {
					q.push(brick(xx, i, map[xx][i]));
				}
				map[xx][i] = 0;
			}
		}
		
			
	}

	sorting();
}

void cop() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			map[i][j] = mapc[i][j];
		}
	}
}

void checking() {
	int count = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (map[i][j] != 0) {
				count++;
			}
		}
	}
	result = result > count ? count : result;
}

brick find(int x) {
	for (int i = 0; i < h; i++) {
		if (map[i][x] != 0) {
			return brick(i, x, map[i][x]);
		}
	}
	return brick(0, 0, 1);
}

void run(int k) {
	if (k == n) {
		int cnt = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] != 0)
					cnt++;
			}
		}
		if (cnt < result) result = cnt;
		return;
	}
	int temp[15][12];
	for (int i = 0; i < 15; i++) {
		for (int j = 0; j < 12; j++) {
			temp[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < w; i++) {
		int x = 0, y = i;
		crush(find(y));
		run(k + 1);
	
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				map[i][j] = temp[i][j];
			}
		}
		
	}
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cin >> n >> w >> h;
		result = 1000000;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
				mapc[i][j] = map[i][j];

			}
		}

		run(0);

		cout << '#' << t<<' '<<result<<endl;
	}
	return 0;
}

상당히 개고생한문제, 처음에 벽돌을 조합으로 주려고했는데, 조합으로 주면 시간초과가 계속나서 그냥 포기했고

재귀로 찾아냈다.