SWEA 5656번 [모의 SW 역량테스트] 벽돌 깨기 C++ DFS, BFS, 시뮬레이션, 구현

리뷰

재귀의 깊이와 맵의 크기가 그리 크지 않아 완전 탐색으로 쉽게 구현이 가능할 줄 알았는데, 생각보다 신경써 주어야 할 것이 많았다... 어렵네 ㅜㅠ 통과한 코드도 시간이 아슬아슬 한 걸 보니 최적화가 더 필요해 보인다...

 

SW Expert Academy

 

문제 풀이

테스트 케이스 tc를 입력 받고 각 테케마다 for문을 돌려주어 init, input, solution 함수를 실행하고 정답 ans를 출력했다.

1. init()

ans값을 10억으로 초기화 해주고, 방문 배열 v를 0으로 초기화 해주었다.

2.input()

n, w, h값을 입력 받아주고 h * w크기의 맵에 벽돌 정보를 받아주었다.

3.solution()

w 범위만큼 dfs를 돌려주었다, 이때 매번 2차 벡터에 맵의 정보를 복사해 주었다.

4.dfs(int level, int col, vector<vector<int>> map)

1. 매개변수 level은 재귀의 깊이이다 초기값은 1, col은 현재 벽돌을 쏠 칼럼의 index이며 map은 현재 단계의 맵 정보이다.
2. 기저조건으로 level이 n을 초과했을 경우 맵에 남은 벽돌을 세어 ans보다 적을 경우 갱신해주고 리턴을 한다.
3. 깨진 벽돌을 저장할 큐 q를 초기화 해주고 해당 큐에 들어올 Pos 구조체는 x, y좌표와 벽돌의 세기이다.
4. flag를 0으로 초기화 해줬다, 만약 현재 col에 부실 벽돌이 없다면 탐색에서 제외해주기 위한 용도이다.
5. 현재 칼럼에서의 각 높이를 탐색해 준다, 맵에서 현재 값이 0일 경우 continue 처리해 준다.
6. 값이 1일 경우 해당 벽돌을 부셔준 뒤 0으로 만들고 flag 처리를 하고 break 해준다.
7. 값이 2이상일 경우 큐에 해당 벽돌 정보를 추가하고 0으로 만들어 준 뒤 bfs를 실행한다.
8. 해당 벽돌의 위치에서 벽돌의 파워만큼 벽돌을 부수고 0으로 만들어 준다, 2이상의 벽돌을 부셨을 경우 큐에 추가
9. 큐가 빌때까지 while을 돌고 이제 중력을 작용시켜 주어 공중에 떠있는 블럭들을 아래로 내려준다.
10. 여기서도 큐 nums를 사용해 주었고 초기 높이는 h, flag를 하나 더 생성해 준다.
11. 아래부터 탐색하여 만약 flag가 작동되지 않은 상태에서 0을 만난다면 flag를 작동해 주고, 해당 높이를 저장한다.
12. flag가 작동된 상태에서 1 이상을 만난 경우 nums에 추가해 준 뒤 해당 좌표를 0으로 만들어 준다.
13. for문이 종료된 후 nums에 저장된 숫자를 0을 처음 만난 높이부터 위로 쭉 쌓아준다.
14. while이 종료되고 마찬가지로 벽돌을 부순 케이스이기 때문에 flag를 체크해 주고 break 처리해 준다.
15. 만약 flag가 작동하지 않았다면 부술 벽돌이 없다는 것이기에 해당 col은 방문처리를 해준다.
16. 이후 모든 열을 탐색하여 방문처리가 되어있지 않을 경우 level을 올려 재귀를 진행해 준다.
17. 재귀를 빠져나왔을 때는 해당 col의 방문처리를 제외해 주어야 한다.
18. 모든 작업을 수행한 뒤 solution 함수가 종료되면 각 테스트 케이스마다 ans값을 출력해 주면 된다.

 

참고 사항

칼럼에 대해 방문처리를 해주지 않았을때 시간 초과가 났다. 부실 벽돌이 없는 케이스를 가지치기 해주면 좋을 것 같다.

현재 pass한 경우에도 시간이 아슬아슬한 상태이므로 최적화가 가능한 부분을 더 체크해 봐야 할 것 같다.

 

정답 코드

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

int tc, n, w, h, ans;
int lst[15][12];
int v[12];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y, p;
};

void init() {
	ans = 1e9;
	memset(v, 0, sizeof(v));
}

void input() {
	cin >> n >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> lst[i][j];
		}
	}
}

void dfs(int level, int col, vector<vector<int>> map) {
	if (level > n) {
		int cnt = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] > 0) cnt++;
			}
		}
		ans = min(ans, cnt);
		return;
	}
	queue<Pos> q;
	int flag = 0;
	for (int i = 0; i < h; i++) {
		if (map[i][col] == 0) continue;
		else if (map[i][col] == 1) {
			map[i][col] = 0;
			flag = 1;
			break;
		}
		else if (map[i][col] > 1) {
			q.push({ i, col, map[i][col] });
			map[i][col] = 0;
			while (!q.empty()) {
				Pos pos = q.front(); q.pop();
				int cx = pos.x, cy = pos.y, cp = pos.p;
				for (int i = 0; i < 4; i++) {
					int nx = cx, ny = cy, np = cp - 1;
					while (np--) {
						nx += dx[i];
						ny += dy[i];
						if (nx < 0 || h <= nx || ny < 0 || w <= ny) break;
						if (map[nx][ny] == 0) continue;
						else if (map[nx][ny] == 1) map[nx][ny] = 0;
						else if (map[nx][ny] > 1) {
							q.push({ nx, ny, map[nx][ny] });
							map[nx][ny] = 0;
						}
					}
				}
			}
			for (int j = 0; j < w; j++) {
				queue<int> nums;
				int first = h, flag = 0;
				for (int i = h - 1; i >= 0; i--) {
					if (flag && map[i][j] > 0) {
						nums.push(map[i][j]);
						map[i][j] = 0;
					}
					if (!flag && map[i][j] == 0) {
						flag = 1;
						first = i;
					}
				}
				while (!nums.empty()) {
					map[first][j] = nums.front();
					nums.pop();
					first--;
				}
			}
			flag = 1;
			break;
		}
	}
	if (!flag) v[col] = 1;
	for (int i = 0; i < w; i++) {
		if (!v[i]) {
			dfs(level + 1, i, map);
			v[i] = 0;
		}
	}
}

void solution() {
	for (int i = 0; i < w; i++) {
		vector<vector<int>> map(h, vector<int>(w));
		for (int j = 0; j < h; j++) {
			for (int k = 0; k < w; k++) {
				map[j][k] = lst[j][k];
			}
		}
		dfs(1, i, map);
	}
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		init();
		input();
		solution();
		cout << "#" << t << " " << ans << "\n";
	}
}