[SWEA] 벽돌깨기

[문제]

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

SW Expert Academy

[풀이]

 

1) 시뮬레이션 문제 (완탐 필요)

 

2) 구슬은 총 n번 떨어뜨릴 수 있기 때문에 DFS cnt == n이면 종료하고 지금 남아있는 벽돌의 개수를 센다. 

 

3) 이 문제에서 중요한 점은 Map을 유지하는 데 있다. 맵을 전역변수로 빼지 않고 계속 변수로 넘겨주면서 보존을 해야한다. 

 

4) 구슬을 떨어뜨리는 dfs는 재귀호출을 하면서 가장 위의 벽돌에 구슬을 떨어뜨린다. 

• 만약 지금 제일 위의 벽돌이 1이라면 자기 자신만 폭파(?) 되고 끝난다. (이번 row는 끝났으므로 break)
• 1이 아니라면 연쇄 폭파되어야 하므로 bomb라는 함수를 호출한다. 
• bomb는 현재 좌표, 현재 맵정보를 넘겨준다. 

5) bomb에서는 일단 현재 좌표의 벽돌을 제거해주고 cnt(연쇄로 떨어뜨려야 하는 값)만큼 상하좌우로 탐색하면서 1이라면 0으로 만들어주고 아니라면 또 연쇄로 폭파시켜야 하기 때문에 큐에 넣는다. 

 

6) 상하좌우 탐색이 끝나면 연쇄로 폭파되어야 하는 것들만 visited처리가 되어있을 것이다. 

그럼 다시 재귀로 호출해서 또 연쇄로 폭파한다. -> 현재 값을 계속 폭파하지 않도록 visited 현재 좌표는 false로 만들어준다. 

 

7) 폭파가 끝나면 다시 dfs의 호출시점으로 되돌아올 텐데 역시 가장 윗 벽돌에 구슬을 떨어뜨렸기 때문에 이번 라인은 끝난다. break처리 

 

8) 구슬을 떨어뜨린 한 라인의 폭발이 끝나면relocateMap()을 호출해서 벽돌을 밑으로 끌어내린다. 

 

 

9) 다시 dfs(cnt+1)을 호출해서 구슬을 떨어뜨린다. 

 

10) cnt==n이라면 벽돌의 최소값을 비교한다. 

---

 

 

#include <iostream> #include <vector> #include <cstring> #include <queue> #define INF 987654321 using namespace std; //SWEA 벽돌깨기 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo int n, w, h, ans; int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0}; typedef pair<int, int> pp; void relocateMap(int (*map)[13]) { //0인 부분이 중간에 껴있으면 밑으로 내려준다. for (int j = 0; j < w; j++) { for (int i = h - 2; i >= 0; --i) { //위에서 벽돌이 시작되는 가장 가까운 좌표 for (int k = i; k < h - 1; k++) { if (!map[k + 1][j]) { swap(map[k + 1][j], map[k][j]); } } } } } bool checkRange(int x, int y) { if (x < 0 || x >= h || y < 0 || y >= w) return false; return true; } int check(int (*map)[13]) { int ret = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (map[i][j]) ret++; } } return ret; } bool noBrick(int (*map)[13]) { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (map[i][j]) return false; } } return true; } void bomb(int x, int y, int (*map)[13]) { queue<pp> q; q.push(pp(x, y)); while (!q.empty()) { int xx = q.front().first; int yy = q.front().second; q.pop(); int cnt = map[xx][yy]; map[xx][yy] = 0; for (int d = 0; d < 4; d++) { for (int k = 1; k < cnt; k++) { int nx = xx + dx[d] * k; int ny = yy + dy[d] * k; if (checkRange(nx, ny)) { if (map[nx][ny] <= 1) { map[nx][ny] = 0; } else { q.push(pp(nx, ny)); } } else break; } } } } void dfs(int cnt, int (*map)[13]) { if (noBrick(map)) { ans = 0; return; } if (cnt == n) { int res = check(map); //남은 벽돌의 개수 ans = min(ans, res); return; } int c_map[16][13]; for (int i = 0; i < w; i++) { //떨어뜨린 곳에 또 떨어뜨릴 수 있다. memcpy(c_map, map, sizeof(c_map)); for (int j = 0; j < h; j++) { if (c_map[j][i]) { if (c_map[j][i] == 1) c_map[j][i] = 0; else { bomb(j, i, c_map); } break; } } relocateMap(c_map); dfs(cnt + 1, c_map); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; int map[16][13]; for (int tc = 1; tc <= t; tc++) { cin >> n >> w >> h; ans = INF; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> map[i][j]; } } dfs(0, map); cout << "#" << tc << " " << ans << '\n'; } return 0; }