반응형
[모의 SW 역량테스트] 벽돌 깨기
1. 이해하기
- 구슬은 N번만 쏠 수 있다.
- 게임의 규칙은 다음과 같다.
- 구슬은 좌, 우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다.
- 벽돌은 숫자 1~9로 표현되며, 구슬이 명중한 벽돌은 상하좌우로 (벽돌에 적힌 숫자-1) 칸 만큼 같이 제거된다.
- 제거되는 범위 내에 있는 벽돌은 동시에 제거된다.
- 빈 공간이 있을 경우 벽돌은 밑으로 떨어지게 된다.
- N 개의 벽돌을 떨어트려 최대한 많은 벽돌을 제거할 때, 남은 벽돌의 갯수를 구하는 문제.
- 완전탐색 + 시뮬레이션 문제.
2. 구현하기
-
구슬이 떨어진 위치에 대한 정보를 줬을 때, 벽돌을 깨트린다.
- 상하좌우로 (벽돌에 적힌 숫자-1) 칸 만큼 같이 제거한다.
void break_brick(vector<vector<int>>& map, int col) { queue<Point> brick; for(int i = 0; i < H; i++) { if(map[i][col] != 0) {brick.push({i,col,map[i][col]}); break;} } while(!brick.empty()) { int x = brick.front().x, y = brick.front().y, range = brick.front().range-1; brick.pop(); map[x][y] = 0; for(int i = x-1; i >= x-range and i >= 0; i--) { if(map[i][y] != 0) brick.push({i,y,map[i][y]}); map[i][y] = 0; } for(int i = x+1; i <= x+range and i < H; i++) { if(map[i][y] != 0) brick.push({i,y,map[i][y]}); map[i][y] = 0; } for(int i = y-1; i >= y-range and i >= 0; i--) { if(map[x][i] != 0) brick.push({x,i,map[x][i]}); map[x][i] = 0; } for(int i = y+1; i <= y+range and i < W; i++) { if(map[x][i] != 0) brick.push({x,i,map[x][i]}); map[x][i] = 0; } } }
-
벽돌의 빈 부분이 생기면 제일 아래까지 떨어트린다.
- 벽돌의 가장 아랫부분을 찾고 이 것을 기준으로 벽돌의 위치를 옮긴다.
vector<int> find_bottom(vector<vector<int>>& map) { vector<int> ret(W,0); for(int i = 0; i < W; i++) { for(int j = H-1; j >= 0; j--) { if(map[j][i] == 0) { ret[i] = j; break; } } } return ret; } void fall_brick(vector<vector<int>>& map) { vector<int> bottom = find_bottom(map); for(int i = 0; i < W; i++) { for(int j = bottom[i]-1; j >= 0; j--) { if(map[j][i] != 0) { map[bottom[i]][i] = map[j][i]; map[j][i] = 0; bottom[i]--; } } } }
-
N개의 구슬을 떨어트리면서 벽돌을 가장 많이 부수는 방법을 찾는다. 그리고 이 때, 남은 벽돌의 갯수를 반환한다.
int count_brick(const vector<vector<int>>& map) { int ret = 0; for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { if(map[i][j] != 0) ret++; } } return ret; } int solve(vector<vector<int>>& map, int cnt) { if(cnt == N) { return count_brick(map); } int ret = W*H; vector<vector<int>> copy = map; for(int i = 0; i < W; i++) { break_brick(map,i); fall_brick(map); ret = min(ret,solve(map,cnt+1)); map = copy; } return ret; }
3. 전체 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Point{
int x,y,range;
};
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N,W,H;
void break_brick(vector<vector<int>>& map, int col) {
queue<Point> brick;
for(int i = 0; i < H; i++) {
if(map[i][col] != 0) {brick.push({i,col,map[i][col]}); break;}
}
while(!brick.empty()) {
int x = brick.front().x, y = brick.front().y, range = brick.front().range-1; brick.pop();
map[x][y] = 0;
for(int i = x-1; i >= x-range and i >= 0; i--) {
if(map[i][y] != 0) brick.push({i,y,map[i][y]});
map[i][y] = 0;
}
for(int i = x+1; i <= x+range and i < H; i++) {
if(map[i][y] != 0) brick.push({i,y,map[i][y]});
map[i][y] = 0;
}
for(int i = y-1; i >= y-range and i >= 0; i--) {
if(map[x][i] != 0) brick.push({x,i,map[x][i]});
map[x][i] = 0;
}
for(int i = y+1; i <= y+range and i < W; i++) {
if(map[x][i] != 0) brick.push({x,i,map[x][i]});
map[x][i] = 0;
}
}
}
vector<int> find_bottom(vector<vector<int>>& map) {
vector<int> ret(W,0);
for(int i = 0; i < W; i++) {
for(int j = H-1; j >= 0; j--) {
if(map[j][i] == 0) {
ret[i] = j;
break;
}
}
}
return ret;
}
void fall_brick(vector<vector<int>>& map) {
vector<int> bottom = find_bottom(map);
for(int i = 0; i < W; i++) {
for(int j = bottom[i]-1; j >= 0; j--) {
if(map[j][i] != 0) {
map[bottom[i]][i] = map[j][i];
map[j][i] = 0;
bottom[i]--;
}
}
}
}
int count_brick(const vector<vector<int>>& map) {
int ret = 0;
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
if(map[i][j] != 0) ret++;
}
}
return ret;
}
int solve(vector<vector<int>>& map, int cnt) {
if(cnt == N) {
return count_brick(map);
}
int ret = W*H;
vector<vector<int>> copy = map;
for(int i = 0; i < W; i++) {
break_brick(map,i);
fall_brick(map);
ret = min(ret,solve(map,cnt+1));
map = copy;
}
return ret;
}
void input(vector<vector<int>>& map) {
cin >> N >> W >> H;
vector<vector<int>> copy(H,vector<int>(W));
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
cin >> copy[i][j];
}
}
map = copy;
}
int main() {
int T;
cin >> T;
for(int t = 1; t <= T; t++) {
vector<vector<int>> map;
input(map);
cout << '#' << t << ' ' << solve(map,0) << '\n';
}
return 0;
}
4. 개선 사항
- solve함수에서 모든 벽돌이 부숴졌을 때, 그대로 0을 리턴하게 하면 수행 시간이 더 빨라진다.
int solve(vector<vector<int>>& map, int cnt) {
if(cnt == N) {
return count_brick(map);
}
int ret = W*H;
vector<vector<int>> copy = map;
for(int i = 0; i < W; i++) {
break_brick(map,i);
fall_brick(map);
ret = min(ret,solve(map,cnt+1));
if(ret == 0) return ret;
map = copy;
}
return ret;
}
'알고리즘 > SW Expert Academy' 카테고리의 다른 글
[모의 SW 역량테스트] 5644. 무선 충전 (0) | 2019.10.19 |
---|---|
[모의 SW 역량테스트] 5658. 보물상자 비밀번호 (0) | 2019.10.19 |
[모의 SW 역량테스트] 5653. 줄기세포배양 (0) | 2019.10.18 |
[모의 SW 역량테스트] 4008. 숫자 만들기 (0) | 2019.10.18 |
[모의 SW 역량테스트] 4012. 요리사 (0) | 2019.10.18 |