[SWEA] 5656. 벽돌 깨기

문제 접근

1. 시뮬레이션 (완전탐색) 문제이다.

2. 가로 길이가 W인 벽돌에 최대 N번 구슬을 쐈을 때 남은 벽돌의 수를 비교하여 가장 적은 수를 출력해야 한다.

3. 문제의 핵심은 완전탐색을 진행하면서 map을 가지고 가는 것이다.
   map을 2차원 배열 형식으로 선언했기 때문에 넘겨 받은 함수에서 해당 map을 사용할 때 유의해야 한다.
   따라서 dfs 함수 내에서 newmap을 선언하여 넘겨 받은 map을 복사하여 사용하고 또 넘겨주었다.

4. 구슬은 현재 쏘고자 하는 위치에서 가장 위쪽에 위치한 벽돌에 부딪힌다.
   구슬이 명중한 벽돌은 상하좌우로 (벽돌에 적힌 숫자 -1) 만큼 같이 제거된다.
   이 과정은 queue를 사용하여 구현, 상하좌우로 제거 시 숫자가 1보다 클 때만 queue에 넣었다.

5. 벽돌이 제거된 이후에는 남은 벽돌들을 아래로 끌어내려야 한다.

6. 만약 현재 위치에서 깨트릴 수 있는 벽돌이 없다면, 남은 벽돌의 수를 센다.
   이때 쏠 수 있는 구슬의 수가 남아 있을 경우 탐색을 계속해서 진행한다.

7. N번 구슬을 쏜 경우, 남은 벽돌의 수를 세고 탐색을 종료한다.

풀이

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#define MAXH 16
#define MAXW 13
using namespace std;

int T, N, W, H, rst;
int map[MAXH][MAXW];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void input() {
	cin >> N >> W >> H;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> map[i][j];
		}
	}
	rst = (MAXH - 1) * (MAXW - 1);
}

int is_range(int x, int y) {
	if (x >= 1 && x <= H && y >= 1 && y <= W) return true;
	return false;
}

void cal_rst(int map[MAXH][MAXW]) {
	int cnt = 0;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (map[i][j]) cnt++;
		}
	}
	rst = min(rst, cnt);
}

void copy_map(int dst[MAXH][MAXW], int src[MAXH][MAXW]) {
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			dst[i][j] = src[i][j];
		}
	}
}

void bomb(int h, int w, int map[MAXH][MAXW]) {
	queue <pair<int, int>> Q;
	int nx, ny, val;
	Q.push(make_pair(h, w));
	while (!Q.empty()) {
		int r = Q.front().first;
		int c = Q.front().second;
		val = map[r][c];
		Q.pop();

		map[r][c] = 0;
		if (val == 1) continue;
		for (int n = 1; n < val; n++) {
			for (int i = 0; i < 4; i++) {
				nx = r + dx[i] * n;
				ny = c + dy[i] * n;
				if (is_range(nx, ny) && map[nx][ny]) {
					Q.push(make_pair(nx, ny));
				}
			}
		}
	}
}

void adjust(int map[MAXH][MAXW]) {
	int temp[MAXH][MAXW] = { 0, };
	for (int w = 1; w <= W; w++) {
		int r = H;
		for (int h = H; h >= 1; h--) {
			if (map[h][w]) {
				temp[r][w] = map[h][w];
				r--;
			}
		}
	}
	copy_map(map, temp);
}

void dfs(int w, int depth, int map[MAXH][MAXW]) {
	int flag = false;
	int newmap[MAXH][MAXW] = { 0, };
	copy_map(newmap, map);
	for (int h = 1; h <= H; h++) {
		if (map[h][w]) {
			bomb(h, w, newmap);
			adjust(newmap);
			flag = true;
			break;
		}
	}
	if (!flag) {
		cal_rst(newmap);
	}
	if (depth == N) {
		cal_rst(newmap);
		return;
	}
	for (int w = 1; w <= W; w++) {
		dfs(w, depth + 1, newmap);
	}
}

void solve() {
	for (int i = 1; i <= W; i++) {
		dfs(i, 1, map);
	}
}

int main() {
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		input();
		solve();
		printf("#%d %d\n", tc, rst);
	}
}

수정된 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#define MAXH 16
#define MAXW 13
using namespace std;

int T, N, W, H, rst;
int map[MAXH][MAXW];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

void input() {
	cin >> N >> W >> H;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> map[i][j];
		}
	}
	rst = (MAXH - 1) * (MAXW - 1);
}

int is_range(int x, int y) {
	if (x >= 1 && x <= H && y >= 1 && y <= W) return true;
	return false;
}

void cal_rst() {
	int cnt = 0;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (map[i][j]) cnt++;
		}
	}
	rst = min(rst, cnt);
}

void copy_map(int dst[][MAXW], int src[][MAXW]) {
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			dst[i][j] = src[i][j];
		}
	}
}

void bomb(int h, int w) {
	queue <pair<int, int>> Q;
	int nx, ny, val;
	Q.push(make_pair(h, w));
	while (!Q.empty()) {
		int r = Q.front().first;
		int c = Q.front().second;
		val = map[r][c];
		Q.pop();

		map[r][c] = 0;
		if (val == 1) continue;
		for (int n = 1; n < val; n++) {
			for (int i = 0; i < 4; i++) {
				nx = r + dx[i] * n;
				ny = c + dy[i] * n;
				if (is_range(nx, ny) && map[nx][ny]) {
					Q.push(make_pair(nx, ny));
				}
			}
		}
	}
}

void adjust() {
	int temp[MAXH][MAXW];
	for (int w = 1; w <= W; w++) {
		int r = H;
		for (int h = H; h >= 1; h--) {
			if (map[h][w]) {
				temp[r][w] = map[h][w];
				r--;
			}
		}
	}
	copy_map(map, temp);
}

void dfs(int w, int depth) {
	int flag = false;
	int c_map[MAXH][MAXW];
	copy_map(c_map, map); // save
	for (int h = 1; h <= H; h++) {
		if (map[h][w]) {
			bomb(h, w);
			adjust();
			flag = true;
			break;
		}
	}
	if (!flag) {
		cal_rst();
	}
	if (depth == N) {
		cal_rst();
		copy_map(map, c_map); // restore
		return;
	}
	for (int w = 1; w <= W; w++) {
		dfs(w, depth + 1);
	}
	copy_map(map, c_map); // restore
}

void solve() {
	for (int i = 1; i <= W; i++) {
		dfs(i, 1);
	}
}

int main() {
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		input();
		solve();
		printf("#%d %d\n", tc, rst);
	}
}

1. 첫 번재 풀이는 save & restore 없이 풀어나갔다. 물론 이렇게 해도 문제는 풀리지만 완전탐색을 비롯한 dfs 문제를 구조적으로 풀기 위해서는 save & restore 과정을 생각하는 습관을 들일 필요가 있다고 판단되어 기존 코드를 수정해 보았다.
2. save & restore 에 해당하는 대상 (이 문제에서는 map)을 잘 선정하고 예외 없이 잘 복구해주는 것이 중요하다. (하나의 node에서의 수행이 끝날 경우, 즉 현 node가 leaf node라고 판정이 날경우 restore를 해주어야 한다.)