[SWEA_모의SW역량테스트] 5656번 - 벽돌 깨기

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

SW Expert Academy

두 번째 SWEA 모의 SW역량테스트 문제다.

이 문제는 

1) 벽돌을 놓는 위치에 대한 모든 순열 고려 (브루트포스)

2) BFS + DFS 완전 탐색

3) 중력에 의해 공의 위치를 조정하는 부분

으로 크게 3개의 모듈로 이루어진 솔루션으로 풀 수 있는 문제다.

 

꽤나 복잡할 수 있지만 규칙에 맞게 하나하나 단계별로 구현해주면 된다.

 

먼저 각 테스트케이스별로 크기와 개수를 입력받아 벡터를 적절한 크기로 초기화 해준 뒤,

make_combination 함수로 순열을 돌면서 놓을 수 있는 조합에 따라 놓고 그 결과와 답의 최소를 답으로 갱신해주면 된다.

 

잊지 말아야 할 것은

1. 한 경우에 대해 모든 공을 던진 후에는 반드시 map, temp, check를 clear()해주어 다음 테스트 케이스에 영향을 주지 않게 하는 것과,

2. 최소값으로 0을 찾은 이후에는 더 이상의 최소값이 존재할 수 없으므로 이 경우에는 추가적인 탐색을 하지 않게 break;를 하는 부분(135번째 라인)을 구현해주어야 한다는 것이다. 이 부분을 안하면 시간 초과로 fail한다.

 

아래는 소스코드.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX_INF 987654321
using namespace std;
int T, N, W, H;
int cnt = 1;
int answer = MAX_INF;
vector<vector<int> > map, temp;
vector<vector<bool> > check;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
void count_nonzero(){
    int this_ans = 0;
    for (int r = 0; r < H; r++){
        for (int c = 0; c < W; c++){
            if (map[r][c]) this_ans++;
        }
    }
    answer = min(answer, this_ans);
}
void resetCheck(){
    for (int r = 0; r < H; r++){
        for (int c = 0; c < W; c++){
            check[r][c] = false;
        }
    }
}
void resetMap(){
    for (int r = 0; r < H; r++){
        for (int c = 0; c < W; c++){
            map[r][c] = temp[r][c];
        }
    }
}
bool make_combination(vector<int>& v){ // 놓는 조합 만들기
    v[N - 1]++;
    int cur_idx = N - 1;
    while (v[cur_idx] == W && cur_idx >= 1){
        v[cur_idx] = 0;
        v[cur_idx - 1] = v[cur_idx - 1] + 1;
        cur_idx--;
    }
    if (v[0] == W) return false;
    return true;
}
void dropBall(int col){
    // 공 놓고 check
    int erase_row = -1;
    for (int row = 0; row <H; row++){
        if (map[row][col]){
            erase_row = row; 
            break;
        }
    }
    if (erase_row == -1) return; // 무효타
 
    queue<pair<int, int> > q;
    check[erase_row][col] = true;
    q.push(make_pair(erase_row, col));
    while (!q.empty()){
        int front_r = q.front().first;
        int front_c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++){
            for (int jump = 0; jump < map[front_r][front_c]; jump++){
                int n_r = front_r + (jump * direction[i].dr);
                int n_c = front_c + (jump * direction[i].dc);
                if (n_r >= 0 && n_r < H && n_c >= 0 && n_c < W){
                    if (!check[n_r][n_c] && map[n_r][n_c]){
                        check[n_r][n_c] = true;
                        q.push(make_pair(n_r, n_c));
                    }
                }
            }
        }
    }
}
void eraseChecked(){
    // check 부분 삭제, 벽돌 재배치
    for (int r = 0; r < H; r++){
        for (int c = 0; c < W; c++){
            if (check[r][c]) map[r][c] = 0;
        }
    }
    for (int c = 0; c < W; c++){
        for (int r = H - 1; r >= 0; r--){
            if (map[r][c]){
                for (int nr = H - 1; nr >= 0; nr--){
                    if (map[nr][c] == 0){
                        if (nr < r){
                            // 0인 곳이 위라면 그냥 끝.
                            break;
                        }
                        else if(nr > r){
                            // 여기에 넣자.
                            map[nr][c] = map[r][c];
                            map[r][c] = 0;
                            break;
                        }
                    }
                }
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    for (int i = 0; i < T; i++){
        answer = MAX_INF;
        cin >> N >> W >> H;
        vector<int> dropPoint(N, 0);
        map.assign(H, vector<int>(W, 0));
        temp.assign(H, vector<int>(W, 0));
        check.assign(H, vector<bool>(W, false));
        for (int r = 0; r < H; r++){
            for (int c = 0; c < W; c++){
                cin >> map[r][c];
                temp[r][c] = map[r][c];
            }
        }
        do{
            for (int j = 0; j < dropPoint.size(); j++){
                dropBall(dropPoint[j]); // map에 체크, curans에 더하기.
                eraseChecked(); // 체크부분 삭제 및 재정렬 
                resetCheck(); // 체크벡터 초기화.
            }
            count_nonzero(); // 정답 갱신.
            resetMap(); // map 다시 초기화.
            if (answer == 0) break;
        } while (make_combination(dropPoint)); // 다음 조합 ㄱ
        cout << "#" << cnt << " " << answer << '\n';
        cnt++;
        map.clear(); temp.clear(); check.clear();
    }
    return 0;
}