C++)SW Expert Academy 벽돌깨기
April 28, 2020
자세한 문제는 벽돌깨기에서 로그인하면 볼 수 있다.
예전에 풀었던 문제라 쉽게 풀 줄 알았는데 중력을 구현하는 부분에서 실수가 있었다.
일단 실수가 있었던 코드는,
//변경 전 중력, 틀린코드
for (int i = h - 2; i > 0; --i) {
for (int j = 0; j < w; ++j) {
if (arr[i][j] != 0 && arr[i + 1][j] == 0) {
int temp = i;
while (1) {
temp++;
if (temp == h || arr[r][j] != 0) break;
}
arr[temp - 1][j] = arr[i][j];
arr[i][j] = 0;
}
}
}아래는 맞은 코드이다
//변경 후 중력, 맞은 코드
for (int i = h - 2; i >= 0; --i) {
for (int j = 0; j < w; ++j) {
if (arr[i][j] > 0 && arr[i + 1][j] == 0) {
int temp = i + 1;
while (1) {
if (temp == h || arr[temp][j] != 0) {
arr[temp - 1][j] = arr[i][j];
arr[i][j] = 0;
break;
}
else if (arr[temp][j] == 0) {
temp++;
continue;
}
}
}
}
}둘 다 테스트케이스는 다 통과했기 때문에 문제를 찾기 쉽지 않았다. 틀린코드는 중력을 적용받지 않을 블록들까지 중력적용을 받아서 틀린코드였고, 아래와 같이 수정하였다.
다음은 전체 코드이다
#include<iostream>
#include<queue>
using namespace std;
int t, n, w, h, ret;
int arr[15][12];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
queue<pair<int, int> > q;
//맵 카피 함수
void cp(int arr1[15][12], int arr2[15][12]) {
for (int i = 0; i < 15; ++i)
for (int j = 0; j < 12; ++j)
arr1[i][j] = arr2[i][j];
}
// 블록을 너비우선탐색으로 지워준다
void bfs() {
while (!q.empty()) {
int r = q.front().first;
int c = q.front().second;
q.pop();
int x = arr[r][c];
//기준이 되는 블록에서 4방향을 지워준다
for (int i = 0; i < 4; ++i) {
int nr = r, nc = c;
//기준이 되는 블록의 숫자만큼 지워준다
for (int j = 1; j < x; ++j) {
nr += dr[i];
nc += dc[i];
if (nr < 0 || nc < 0 || nr >= h || nc >= w)break;
if (arr[nr][nc] != 0) {
q.push({ nr,nc });
}
}
}
arr[r][c] = 0;
}
//중력
for (int i = h - 2; i >= 0; --i) {
for (int j = 0; j < w; ++j) {
//만약 블록이 떠있으면,
if (arr[i][j] > 0 && arr[i + 1][j] == 0) {
int temp = i + 1;
while (1) {
//블록 밑에 땅이 있으면
if (temp == h || arr[temp][j] != 0) {
arr[temp - 1][j] = arr[i][j];
arr[i][j] = 0;
break;
}
//땅이 아니면
else if (arr[temp][j] == 0) {
temp++;
continue;
}
}
}
}
}
}
//깊이우선탐색으로 모든 경우의수를 체크한다
void dfs(int depth) {
if (depth == n) {
int temp = 0;
//살아남은 블록의 개수를 세고
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (arr[i][j] != 0)
temp++;
}
}
//최소값을 구한다
if (ret > temp)ret = temp;
return;
}
int arr_temp[15][12];
for (int i = 0; i < w; ++i) {
//깊이 1 추가하기 전 맵 저장
cp(arr_temp, arr);
//블록이면 bfs실행
for (int j = 0; j < h; ++j) {
if (arr[j][i] != 0) {
q.push({ j,i });
bfs();
break;
}
}
dfs(depth + 1);
//저장된 맵 불러오기
cp(arr, arr_temp);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> t;
for (int i = 0; i < t; ++i) {
cin >> n >> w >> h;
for (int j = 0; j < h; ++j)
for (int k = 0; k < w; ++k)
cin >> arr[j][k];
ret = 100000;
dfs(0);
cout << '#' << i + 1 << ' ' << ret << '\n';
}
return 0;
}