[모의 SW 역량테스트] 5656. 벽돌 깨기

[모의 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;
}