SWEA 5656번: [모의 SW 역량테스트] 벽돌 깨기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

SW Expert Academy

모의 역량테스트 두 번째 풀이 벽돌깨기다

알고리즘 짜는데는 5분도 안 걸렸는데 디버깅에서 막혔다

ㅠㅠ

 

 

좌: 벽돌의 크기만큼의 상하좌우 벽돌을 깬다                                  우 : 연쇄작용도 한번에 발생한다

벽돌깨기가 다 끝나고 나면 중력으로 밑으로 내려준다

전형적인 DFS를 이용한 경우의 수 완전탐색 문제이다

1. N번 이동을 끝내고 나면 남은 벽돌의 개수 세주기

2. 턴마다 해당 열의 맨 위의 벽돌 깨기 & 중력 연산 수행

 

이 두가지만 잘 해주면 된다

나는 벽돌깨는 함수boom(), 중력 작용하는 함수gravity()를 이동의 경우의수(N번이동했을 때 W열)에 적용시켜 주어 Solve했다.

 

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int n, h, w, tc, ans = 5000, map[16][13], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
typedef struct {
	int x, y;
}point;
stack<int> s;
bool safe(int x, int y) {
	return x >= 0 && x < w && y >= 0 && y < h;
}
void gravity() {
	for (int a = 0, b=0; a < w; a++) {
		for(b=0;b<h;b++)
			if (map[b][a]) {
				s.push(map[b][a]);
				map[b][a] = 0;
			}
		for (b = h - 1; b >= 0; b--)
			if (!s.empty()) {
				map[b][a] = s.top();
				s.pop();
			}
	}
}
void boom(point p) {
	point cur; int k = map[p.y][p.x];
	map[p.y][p.x] = 0;
	if (k > 1)
		for (int i = 0; i < 4; i++) {
			cur = p;
			for (int j = 0; j < k - 1; j++) {
				cur.x += dx[i]; cur.y += dy[i];
				if (!safe(cur.x, cur.y))break;
				if (map[cur.y][cur.x] > 1)
					boom(cur);
				else map[cur.y][cur.x] = 0;
			}
		}
}
void dfs(int dep) {
	if (dep == n) {
		int sum = 0;
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				if (map[i][j])sum++;
		if (sum < ans)
			ans = sum;
		return;
	}
	int temp[13][16],check=0;
	memcpy(temp, map, sizeof(map));

	for (int j = 0, i = 0; j < w; j++) {
		for (i=0;i<h;i++) 
			if (map[i][j])break;
		if (i == h)continue;
		check = 1;
		boom({ j,i });
		gravity();
		dfs(dep + 1);
		memcpy(map, temp, sizeof(map));
	}
	if (!check)ans = 0;
}
int main() {
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		scanf("%d%d%d", &n, &w, &h);

		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				scanf("%d", &map[i][j]);

		dfs(0);
		printf("#%d %d\n", t, ans);
		ans = 5000;
	}
	return 0;
}

 

++Tip. ⭐Stack Overflow 계산하고 배열 인덱스 범위 넘어가는 연산 있는지 꼭 체크할 것 !!⭐