5656.벽돌깨기

이번문제는 SW Expert의 벽돌깨기이다. 정답률은 60% 정도지만 솔직히 말도안되는거같다..

난이도가 상당히 높게 느껴졌고 정답률이 크게 의미가 없다는 생각이 들었다... (내가 못하는건가.. 쩝..)

구현은 하나하나씩 필요한 것들을 구현했고 어떻게 푸는 줄은 알겠는데 아직도 구현이 안되는 부분들이 있었다.

그런 부분들은 구글링을 통해서 진행했다. 그럼에도 불구하고 테스크케이스 50개중 47개만 맞았다..

결국 질문을 올렸고 check 배열을 초기화하는 순서가 잘못되었다는 것을 알게되었다 ( 답변자분 감사합니다ㅠ )

SW Expert Academy

문제 자체는 어렵다는 생각이 들지만 도움은 많이되는 문제인 것 같다. 여러분들께 한번 풀어보라고 추천해주고 싶다!!

나도 시간이 조금 지나면 다시 풀어봐야겠다..

---

 

이 문제를 풀때 필요한 로직은 크게 다음과 같다.

1. 벽돌을 깨기시작할 공이 떨어질 위치 -> 공이 떨어질 위치에 대한 로직 ( 벽돌이 존재하는 곳부터 시작되도록).

2.벽돌이 깨지면서 벽돌속의 숫자만큼 연쇄적으로 깨지는 로직

이 밖에도 세세한로직들이 필요한데 요즘 시뮬레이션을 풀면서 느끼는 것중에 가장 중요한 것은

1. 구현  /  2.구현한 내용을 엮어서 설계하는 것 => 이라고 생각한다.. 나는 2번이 특히 어렵다..

구현을 아무리잘해도 잘엮지못하면 문제를 풀어낼 수가 없다..

 

---

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <string.h>
 
#define HIG 16
#define WID 13
using namespace std;
 
int map[HIG][WID];
bool check[HIG][WID];
 
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
int T, N, W, H;
int min_count = 987654321;
 
void copy(int(*a)[WID], int(*b)[WID]) { // 배열 복사 함수
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            b[i][j] = a[i][j]; // a배열을 b에 복사
        }
    }
}
 
void init(){ // 초기화 함수
    min_count = 987654321;
    memset(map, 0, sizeof(map));
    memset(check, 0, sizeof(check));
}
 
void boom(int x, int y){ // 벽톨이 연쇄적으로 터지는 함수
    check[x][y] = true;
    int len = map[x][y];   // 해당 벽돌의 값
    for (int j = 1; j <= len - 1; j++){ // 벽돌의 크기만큼 점점 탐색범위를 늘리기위함임
        for (int i = 0; i < 4; i++){
            int ax = x + dx[i] * j; // 곰셈을 통해 탐색 위치 거리값 증가
            int ay = y + dy[i] * j;
            if (ax < 0 || ay < 0 || ax >= H || ay >= W) // 범위초과시 그냥 넘김
                continue;
            if (!check[ax][ay] && map[ax][ay]){ // 탐색한적이 없거나 벽돌이 있는 경우에만
                check[ax][ay] = true; // 해당 위치 탐색표시
                if (map[ax][ay]){ // 벽돌이 있는 경우에는 boom() !! 진행
                    boom(ax, ay); // 재귀함수로 연쇄작용
                }
            }
        }
    }
    map[x][y] = 0; // 터짐 후 벽돌 사라짐
    return;
}
 
void drop_wall(){ // 벽돌 파괴 후 벽돌이 떨어지면서 정리되는 함수
    for (int i = 0; i < W; i++){
        for (int j = H - 1; j >= 0; j--){
            if (map[j][i]){ // 벽돌이 있다면
                int x, y;
                x = i, y = j;
                while (true){
                    if (map[y + 1][x] || y + 1 >= H) // 벽돌이 떨어지다가 바닥을 뚫는 범위가 되거나 벽돌을 만나면 그만둔다.
                        break;
 
                    // 그게아니면
                    map[y + 1][x] = map[y][x]; // 벽돌의 위치를 옮기고
                    map[y][x] = 0; // 옮겨진 위치를 비움
                    y++; // 좌표 +1
                }
            }
        }
    }
}
 
void game_start(int n){
    int copy_map[HIG][WID];
    copy(map, copy_map); // map을 copy_map에 복사해둠
    if (n == N){ // 공을 다 떨어뜨렸다면
        int cnt = 0;
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                if (map[i][j]) // 남아 있는 벽돌을 count
                    cnt++; 
            }
        }
        if (cnt < min_count) // 남아있는 벽돌의 최솟값을 구함
            min_count = cnt;
        return;
    }
 
    for (int i = 0; i < W; i++){ 
        int x = 0, y = i;
        while (map[x][y] == 0 && !(x < 0 || y < 0 || x >= H || y >= W))  // 공이 떨어지는 곳에 블록이 없거나 범위를 초과하는 경우
            x++;  //아래로 계속 내려가면서 벽돌을 찾음
        memset(check, 0, sizeof(check)); //check배열 초기화
        boom(x, y); // 시작 x좌표, y좌표
        drop_wall();// 벽돌이 파괴후 남은 벽돌들 중력에 의해 떨어짐
        game_start(n + 1); // 다음 공을 떨어뜨림(재귀함수 사용)
        copy(copy_map, map); // 파괴된 copy_map을 map에 복사
    }
}
 
int main() {
    freopen("5656.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        init();
        cin >> N >> W >> H;
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                cin >> map[i][j];
            }
        }
        game_start(0);
        cout << "#" << z << " " << min_count << "\n";
    }
    return 0;
}

# 문제는 재미있지만 살짝 복잡한거 같다...ㅎㅎ