[SWEA] 5656번 벽돌 깨기 (C++)

SW Expert Academy

1. findTop

0열부터 W - 1열까지 돌면서

0행부터 탐색하며

맨 위에 있는 벽돌을 찾아내는 함수이다.

이 행위를 재귀로 N번 반복하면

N개 중 N개를 중복 포함에서 뽑는 중복 순열이 된다.

 

맨 위에 있는 벽돌을 찾아내면 거기에 구슬을 떨어뜨리고 

다음 동작들을 (연쇄 벽돌 없애기, 벽돌 재 정렬하기) 실행한 뒤

돌아와서 재귀로 구슬을 떨어뜨릴 다음 위치를 찾는다.

 

2. findChain

구슬을 떨어뜨린 벽돌을 기준으로

연쇄된 모든 벽돌을 찾아 0으로 바꿔주는 함수이다.

상하좌우를 DFS 탐색하며 

명중된 벽돌들을 찾아서 큐에 넣어준 뒤

0으로 바꿔주고 다음 큐로 넘어간다.

 

3. dropBricks

중간중간에 빈 공간이 생긴 벽돌을 재 정렬하는 함수이다.

열 단위로 스택에 벽돌 종류를 담아준 다음

맨 밑에서부터 pop해준 뒤

나머지 공간엔 0으로 채워준다.

 

4. countBricks

남은 벽돌의 개수를 카운트하는 함수이다.

findTop을 N번 반복하지 못 하는 경우도 있기 때문에

재귀로 N번 반복했을 때 뿐만 아니라

반복문이 끝나고 나서도 호출해 주어야 한다.

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <climits>
using namespace std;

class info {
public:
	int x, y, num;
	info(int x, int y, int num) {
		this->x = x;
		this->y = y;
		this->num = num;
	}
};

int N, W, H, tot, res;
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
queue<info> shoot; // 명중하는 벽돌 위치 저장
stack<int> brick; // 재정렬 위해 벽돌 종류 저장

void countBricks(int newArr[][13]) {
	int cnt = 0;
	for (int m = 0; m < H; m++) for (int k = 0; k < W; k++) if (newArr[m][k] > 0) cnt++; // 남은 벽돌 개수 세기
	res = min(res, cnt);
}

void dropBricks(int newArr[][13]) { // 남은 벽돌들 재정렬
	for (int j = 0; j < W; j++) {
		for (int i = 0; i < H; i++) if (newArr[i][j] > 0) brick.push(newArr[i][j]);
		for (int i = H - 1; i >= 0; i--) {
			if (!brick.empty()) {
				newArr[i][j] = brick.top(); // 밑에서부터 벽돌 채워 넣음
				brick.pop();
			}
			else newArr[i][j] = 0; // 나머지는 0으로 채워 넣음
		}
	}
}

void findChain(int X, int Y, int newArr[][13]) { // 연쇄 벽돌들 찾기 - DFS
	bool chk[16][13] = { false }; // 방문 체크
	shoot.push(info(X, Y, newArr[X][Y]));
	newArr[X][Y] = 0;
	while (!shoot.empty()) {
		for (int i = 0; i < 4; i++) {
			int x = shoot.front().x, y = shoot.front().y, cnt = shoot.front().num;
			while (--cnt > 0) {
				x += dx[i], y += dy[i];
				if (x < 0 || x >= H || y < 0 || y >= W) break; // 범위 벗어나면 나옴
				if (newArr[x][y] > 0) shoot.push(info(x, y, newArr[x][y]));
				newArr[x][y] = 0;
			}
		}
		shoot.pop();
	}
}

void findTop(int arr[][13], int n) { // 맨 위의 벽돌 찾기 - 중복 순열
	if (n == N) {
		countBricks(arr);
		return;
	}
	for (int j = 0; j < W; j++) { // 각 열마다 맨 위의 벽돌 찾기
		int i = -1;
		while (true) if (++i == H || arr[i][j] > 0) break; // 범위를 벗어나거나 벽돌이면 나온다
		if (i == H) continue; // 벽돌이 없으면 다음 열로 이동

		int newArr[16][13] = { 0 };
		copy(&arr[0][0], &arr[0][0] + 16 * 13, &newArr[0][0]); // 이차원 배열 복사 후 사용
		findChain(i, j, newArr);
		dropBricks(newArr);
		findTop(newArr, n + 1);
	}
	countBricks(arr); // 재귀로 못 넘어가는 경우도 있기 때문에 여기서도 res 갱신 시켜준다.
}

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N >> W >> H;
		int arr[16][13] = { 0 };
		for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> arr[i][j];
		res = INT_MAX;
		findTop(arr, 0);
		cout << "#" << t << " " << res << "\n";
	}

	return 0;
}

 

저번 달에 시도했을 때

명중한 벽돌을 없애지 않고 체크 배열로 표시만 해두면서 풀었더니

상하좌우에 위치한 유효 벽돌을 골라내는 게 너무 힘들어서

다음에 다시 풀어봐야지~ 하고 미룬 지 한 달이 지났다..

 

과제로 나와버린 김에 (강제로) 다시 직면했으나

몇 시간 내내 또 같은 실수를 반복하고 있는 나를 발견하고

그냥 문제에 나와있는 그대로

벽돌을 명중시키면 쿨하게 없애버리는 동작을 단계별로 구현해보았다.

그러니까 갑자기 술술 풀리길래 허무했다.

 

이 방법이 더 귀찮을 거 같아서 안 움직이고 체크만 하는 방식을 고집했었는데

오히려 그 반대였던 게 함정ㅠㅠ

언제쯤 시뮬레이션 문제를 고통받지 않고 한 번에 구현해낼 수 있을까,,