[SWEA] 5656 벽돌깨기

5656 벽돌깨기

풀이)

모든 경우를 확인해보는 문제였다.

처음에 

없애는 벽돌에 적힌 숫자만큼이나 상하좌우 다른 벽돌을 제거하는 걸 어떻게 처리할까 싶었는데

그냥 벽돌에 적힌 수만큼 상하좌우 모두 방문 해보고 바꿔주면 되었다.

-> 다 방문한다!!

간단히 풀이과정을 말해보자면

1. dfs을 통해 어떤 행의 벽돌을 없앨 건지, 행들의 순열(n개 길이)을 구한다.

2. 그 순열 순서대로 벽돌을 없애고, 벽돌을 내리는 행위를 반복한다.

  -> 벽돌없애는 과정도 dfs를 통해 없앤다.

벽돌을 없애는 함수는  -> change()

벽돌을 내리는 함수는 -> relocate()

주의할 점

재귀 방법을 이용해서 벽돌을 없애므로, 이전 상태의 값을 저장해놓고

되돌아 왔을 때 원래 값으로 다시 바꿔줘야한다는 점이다.

코드)

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
 
#define INF 999999999
 
int n, w, h;
vector <vector<int>> map;
 
int result;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
bool check_range(int y, int x) {
    if (x >= 0 && y >= 0 && x < w && y < h)
        return true;
    else
        return false;
}
 
void change(int y, int x) {
    if (!check_range(y, x))return;
    if (map[y][x] == 0) return;
 
    int len = map[y][x];
    map[y][x] = 0;
    
    for (int i = 1; i < len; i++) //벽돌에 적힌 수만큼 상하좌우 모두 이동
    {
        for (int j = 0; j < 4; j++)//상하좌우
        {
            int ny = y + dy[j] * i;
            int nx = x + dx[j] * i;
            
            if (check_range(ny, nx) && map[ny][nx] != 0)
                change(ny, nx);
        }
    }
}
 
void relocate() {
    for (int i = 0; i < w; i++) {
        for (int j = h - 1; j >= 1; j--) {
            for (int k = j - 1; k >= 0; k--) {
                if (map[j][i] != 0) break;
                if (map[k][i] != 0) {
                    map[j][i] = map[k][i];
                    map[k][i] = 0;
                    break;
                }
            }
        }
    }
}
 
 
void dfs(int depth) {
    
    if (depth == n) {
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] > 0) cnt++;
            }
        }
        result = min(result, cnt);
        return;
    }
 
    vector <vector<int>> temp = map;//상태 저장
    for (int i = 0; i < w; i++) {
        int y = 0;
        while (check_range(y, i)&&map[y][i] == 0)
        {
            y++;
        }
        change(y,i); //i번째 행의 벽돌 깨기 
        relocate(); // 벽돌 떨굼
        dfs(depth + 1);
 
        //원래값으로 돌려놓음
        map = temp;
    }
}
 
int main() {
    //freopen("sample_input (1).txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    map.resize(15);
    for (int i = 0; i < 15; i++) {
        map[i].resize(12);
    }
    for (int test_case = 1; test_case <= T; test_case++) {
        result = INF;
        scanf("%d %d %d", &n, &w, &h);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                scanf("%d", &map[i][j]);
            }
        }
        dfs(0);
        printf("#%d %d\n", test_case, result);
    }
    return 0;
}