[Algorithm][C++] SWEA 5656. [모의 SW 역량 테스트] 벽돌 깨기

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

SW Expert Academy

 

풀이 핵심

1. Back Tracking, Bruth Force 문제 (완전 탐색 문제!)

 

2. 두가지 함수만 잘 구현 하면 쉽게 풀 수 있다.

-  void shooting(int c) 함수

• c 열에 구슬을 쏘아 벽돌을 제거하는 함수
• target이라는 큐에 구슬을 맞춘 위치 (r, c)를 저장하고 상, 하, 좌, 우 제거 가능한 블록을 removal 배열에 표시한다. 그리고 제거할 블록 위치 정보를 큐에 넣는다. 큐가 비어 있을 때까지 이를 반복한다.
• 큐가 모두 비었다면 removal에 표시된 블록들을 모두 0으로 만든다.

 

- void sorting() 함수

• 각 열마다 테트리스와 같이 밑으로 내려준다.
• 빈 곳의 행(r)을 target에 저장 하고 r을 감소해가며 target에 블록들의 값을 넣는다.

 

3. solve 라는 재귀 함수로 문제를 완전 탐색 한다. 전달 인자는 구슬을 쏜 횟수 cnt, 현재 보드 cur로 이루어져 있다.

구슬을 쏜 횟수가 N과 같으면 get_remaining_block 함수를 사용해 현재 남은 블록의 개수와 ans 개수와 비교한다.

구슬을 쏜 횟수가 N보다 작으면 shooting, sorting을 진행해준다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
#define MAXW	12
#define MAXH	15

using namespace std;

int N, W, H;

struct Pos {
	int r, c;
};
const int dr[] = { 0,1,0,-1 };
const int dc[] = { -1,0,1,0 };

struct Board {
	int map[MAXH][MAXW];

	void shooting(int c) {
		queue<Pos> target;
		int r = 0;
		bool removal[MAXH][MAXW] = { 0, };
		while (r < H && map[r][c] == 0) {
			r++;
		}
		if (r == H) {
			return;
		}
		removal[r][c] = true; // 제거 표시
		target.push({ r,c });
		while (!target.empty()) {
			Pos cur = target.front();
			target.pop();
			int range = map[cur.r][cur.c]; // 블록이 폭탄 처럼 영향을 미치는 범위
			for (int dir = 0; dir < 4; dir++) {
				int nr = cur.r, nc = cur.c;
				for (int i = 0; i < range - 1; i++) { // 꼭 rnage에 -1 해줘야 한다
					nr += dr[dir], nc += dc[dir];
					if (nr < 0 || nr >= H || nc < 0 || nc >= W) {
						break;
					}
					if (map[nr][nc] && !removal[nr][nc]) {
						removal[nr][nc] = true; // 제거 표시
						target.push({ nr,nc });
					}
				}
			}
		}

		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				if (removal[r][c]) {
					map[r][c] = 0; // 제거 표시가 된 블록 제거
				}
			}
		}
	}

	void sorting() {
		for (int c = 0; c < W; c++) {
			int target = H - 1; // 블럭을 넣어야 할 곳
			while (target >= 0 && map[target][c]) {
				target--;
			}
			if (target <= 0) { // 0이 포함 되어 있는 이유는 0위에는 아무런 블록이 없으므로
				continue;
			}
			int r = target;
			while (r != 0) {
				r--;
				if (map[r][c]) {
					map[target--][c] = map[r][c];
					map[r][c] = 0;
				}
			}
		}
	}

	int get_remaining_block() { // 현재 남은 블록 return
		int ret = 0;
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				if (map[r][c]) {
					ret++;
				}
			}
		}
		return ret;
	}
};
Board board;
int ans;

inline int min(int a, int b) {
	return a < b ? a : b;
}

void solve(int cnt, Board cur) {
	if (cnt == N) {
		int candi = cur.get_remaining_block();
		ans = min(ans, candi);
		return;
	}

	for (int c = 0; c < W; c++) {
		Board next = cur;
		next.shooting(c);
		next.sorting();
		solve(cnt + 1, next);
	}
}

int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d %d %d", &N, &W, &H);
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				scanf("%d", &board.map[r][c]);
				if (board.map[r][c]) {
					ans++; // 최소 남은 블록을 구해야 하므로
				}
			}
		}
		solve(0, board);
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}

 

shooting, sorting 함수만 잘 구현해 준다면 쉽게 풀 수 있다.