[SWEA] 5656번: 벽돌 깨기

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

SW Expert Academy

 

문제 이해

아이디어 내기는 어렵지 않다.

어차피 최대 4번 벽돌 던질 수 있으니까 DFS로 벽돌 열 번호를 고르고 시뮬레이션을 돌려보면 된다.

나는 그나마 시간을 단축하기 위해서 모든 단계마다 시뮬을 돌려주었다. 

(벽돌 하나 던지고 다음 단계로 넘어가고 이런식으로, 그럼 같은 부수기 동작을 훨씬 덜 할 수 있다.

다 던지고서 시뮬레이션을 돌리지 말라는 뜻)

 

내가 헤맸던 건 별 것도 아닌 W가 가로고 H가 세로인데, 입력 받을 때 거꾸로 받고 있었다.

 

그리고 하나 더, 예제 5번에 걸리는 거긴 한데,

만약 N번 벽돌을 던지기 전에 모든 벽돌이 사라졌으면 꼭 그냥 리턴하도록 해줘야 한다!

실전에서 이런 예외 사항을 잊지 않아야 할 것이다

 

사소한 실수만 아니었으면 금방 풀었을 문제......ㅠ

 

작성 코드

#include <stdio.h>
#include <string.h>
// width 중에 4개 고르고
// 시뮬 돌려보면 됨
#define MAXW 12
#define MAXH 15

int T;
int map[MAXW + 5][MAXH + 5];
int visited[MAXW + 5][MAXH + 5];
int N, W, H;
int max;
int crushed_cnt;

int blocks;
int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };

void Init(void) {
	max = 0;
	memset(visited, 0, sizeof(visited));
	blocks = 0;
	memset(map, 0, sizeof(map));
}

void Get_Input(void) {
	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]);
			if (map[i][j] != 0) blocks++;
		}
	}
}

int Find_Target(int x) {
	// i번째에 벽돌 떨어뜨림
	int y = 0;
	int d = 0;
	for (y = 0; y < H; y++) {
		if (map[y][x] == 0) continue;
		// 찾음
		return y;
	}
}

typedef struct st {
	int y, x, d;
}ELE;
ELE q[MAXW * MAXH * 10];
int wp, rp;
void enq(int y, int x, int d) { q[wp].y = y, q[wp].x = x, q[wp++].d = d; }
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }

int Break_Bricks(int y, int x) {
	int cnt = 0;
	wp = rp = 0;
	memset(visited, 0, sizeof(visited));

	if (map[y][x] == 0) return 0;
	enq(y, x, map[y][x]);
	visited[y][x]++;
	map[y][x] = 0;
	cnt++;

	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 4; i++) {
			for (int j = 1; j < cur.d; j++) {
				int ny = cur.y + dy[i] * j;
				int nx = cur.x + dx[i] * j;
				if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
				if (visited[ny][nx] >= 1) continue;
				if (map[ny][nx] == 0) continue;
				enq(ny, nx, map[ny][nx]);
				visited[ny][nx]++;
				map[ny][nx] = 0;
				cnt++;
			}
		}
	}
	return cnt;
}

void Pull_Down(void) {
	for(int j = 0; j<W; j++){
		for (int i = H - 1; i > 0; i--) {
			if (map[i][j] == 0) {
				for (int k = i - 1; k >= 0; k--) {
					if (map[k][j] != 0) {
						int tmp = map[i][j];
						map[i][j] = map[k][j];
						map[k][j] = tmp;
						break;
					}
				}
			}
		}
	}
}

int Simulation(int x) {
	
	int y = Find_Target(x);
	int res = Break_Bricks(y, x);
	Pull_Down();
	return res;
}

void DFS(int cnt, int crushed, int idx) {

	// 종료
	if (cnt == N) {
		if (crushed > max) max = crushed;
		return;
	}

	// 재귀
	int tmp[MAXW + 5][MAXH + 5];
	memcpy(tmp, map, sizeof(tmp));
	for (int i = 0; i < W; i++) {
		int res = Simulation(i);
		DFS(cnt+1, crushed + res, i);
		memcpy(map, tmp, sizeof(tmp));
	}

}

int main(void) {
	scanf("%d", &T);
	for(int t = 1; t<=T; t++){
		Init();
		Get_Input();
		DFS(0, 0, 0);
		printf("#%d %d\n", t, blocks-max);
	}
	return 0;
}