[SWEA] #5656 _ 벽돌 깨기

[벽돌 깨기] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

벡터를 사용하여 벽돌을 세로가 아닌 가로로 저장하고, 가장 끝에 있는 값을 깨는 방법으로 구현하였다.

(erase를 사용하여 가운데 값을 삭제해도 앞으로 땡기는 작업을 하지 않기 위해 벡터 사용)

하지만, 직관적으로 보기에는 배열을 이용하는게 좋은 것 같다..;;

 

깰 수 있는 모든 경우의 수를 다 돌려 가장 벽돌이 적게 남은 경우를 출력하였다.

모든 경우의 수를 하지 않는 방법을 생각하다가,,,

제한 시간이 3초인 것을 보고 모든 경우의 수를 다 돌려보기로 결정하였다.

 

벽돌을 제거할 때, 상하좌우로 제거되기 때문에 bfs를 이용하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_W 12
#define MAX_H 15

using namespace std;
vector<vector<int> > tmp_map, map;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
int n, w, h;
int remain, bp = 0;

int solve(int count, int block_loc[]);
void break_bfs(pair<int, int> x_y);
int count_block();
int main() {
	int test_case, tmp;

	scanf("%d", &test_case);
	for (int k = 1; k <= test_case; k++) {
		int loc[5] = { 0, };
		map = vector<vector<int> >(MAX_W + 1, vector<int>(MAX_H + 1, 0));
		remain = 999999;
		bp = 0;

		scanf("%d %d %d", &n, &w, &h);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				scanf("%d", &tmp);
				map[j].insert(map[j].begin(), tmp);
			}
		}

		solve(0, loc);
		printf("#%d %d\n", k, remain);
	}

	return 0;
}

int solve(int count, int block_loc[]) {
	if (bp == 1) return 0;
	if (count == n) {
		tmp_map.clear();
		tmp_map.assign(map.begin(), map.end());
		for (int i = 0; i < n; i++) {
			int x = block_loc[i];
			int y = find(tmp_map[x].begin(), tmp_map[x].end(), 0) - tmp_map[x].begin() - 1;
			if (y < 0) break;
			break_bfs(make_pair(x, y));
		}
		remain = min(remain, count_block());
		if (remain == 0) bp = 1;
		return 0;
	}
	for (int i = 0; i < w; i++) {
		block_loc[count] = i;
		solve(count + 1, block_loc);
	}

	return 0;
}

void break_bfs(pair<int, int> x_y) {
	queue<pair<int, int> > q;
	queue<int> range;
	priority_queue<pair<int, int> > del;
	pair<int, int> tmp;
	int x, y, break_size;

	q.push(x_y);
	range.push(tmp_map[x_y.first][x_y.second]);
	tmp_map[x_y.first][x_y.second] = 0;
	del.push(make_pair(x_y.first, x_y.second));

	while (!q.empty()) {
		tmp = q.front();
		break_size = range.front();
		q.pop();
		range.pop();

		for (int i = 1; i < break_size; i++) {
			for (int j = 0; j < 4; j++) {
				x = tmp.first + (dx[j] * i);
				y = tmp.second + (dy[j] * i);
				if (x < 0 || y < 0 || x >= w || y >= h) continue;
				if (tmp_map[x][y] == 0) continue;
				if (tmp_map[x][y] > 1) {
					q.push(make_pair(x, y));
					range.push(tmp_map[x][y]);
				}
				tmp_map[x][y] = 0;
				del.push(make_pair(x, y));
			}
		}
	}

	while (!del.empty()) {
		tmp = del.top();
		del.pop();
		tmp_map[tmp.first].erase(tmp_map[tmp.first].begin() + tmp.second);
	}
}

int count_block() {
	int count = 0;

	for (int i = 0; i < w; i++) {
		for (int j = 0; j < h; j++) {
			if (tmp_map[i][j] == 0) break;
			count++;
		}
	}

	return count;
}