5656번 벽돌 깨기

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

2차원 배열을 백트래킹 함수의 인자로 넘겨주는 것이 핵심인 것 같다. 

다시 풀어볼 문제이고, 복습할 문제이다.

2차원 배열을 복사하는 C++ STL이 있는지 잘 몰라서, 

그냥 이중 for문으로 구현하였다.

복습

2019년 10월 19일 토요일 다시 복습할겸 푼 코드다. 맨 아래에 최초의 정답 코드가 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 17
 
int N, W, H, answer = Max * Max;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max];
 
void update(int(*m)[Max]) // 블록들을 내린다
{
    for (int j = 0; j < W; j++)
        for (int i = H - 1; i >= 0; i--)    
            if (m[i][j]) // 블록이라면
            {
                int r = i;
                while (r + 1 < H && !m[r + 1][j]) { ++r; } // 숫자 블록(r + 1)을 만나기까지 진행
                swap(m[i][j], m[r][j]); // 숫자 블록 바로 위(r)와 교환
            }
}
 
void dfs(int(*m)[Max], int r, int c)
{
    visit[r][c] = true;
    int k = m[r][c] - 1;
    m[r][c] = 0;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r, x = c; // r과 c는 변해서는 안 되므로, y, x 변수 활용
 
        for (int j = 0; j < k; j++)
        {
            y += dy[i]; // 누적해야함
            x += dx[i]; // 누적해야함
            if (y < 0 || y >= H || x < 0 || x >= W || visit[y][x]) continue;
            dfs(m, y, x);
        }
    }
}
 
void bt(int (*m)[Max], int cnt)
{
    int rm = 0;
 
    for (int i = 0; i < H; i++) 
        for (int j = 0; j < W; j++)        
            if (m[i][j])
                ++rm;
 
    answer = min(answer, rm);
 
    if (cnt == N) return;
 
    int temp[Max][Max];
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++)    temp[i][j] = m[i][j];
 
    for (int j = 0; j < W; j++)
    {
        int r = -1;
        for (int i = 0; i < H; i++) if (m[i][j]) { r = i; break; }    
        if (r == -1) continue;
        memset(visit, false, sizeof(visit));
        dfs(m, r, j);
        update(m);    
        bt(m, cnt + 1);
        for (int R = 0; R < H; R++) for (int C = 0; C < W; C++) m[R][C] = temp[R][C];    
    }
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
 
    int test_case;
 
    scanf("%d", &test_case);
 
    for (int tc = 1; tc <= test_case; tc++)
    {
        answer = Max * Max;
        int m[Max][Max];
 
        scanf("%d %d %d", &N, &W, &H);
        for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) scanf("%d", &m[i][j]);
 
        bt(m, 0);
 
        printf("#%d %d\n", tc, answer);
    }
 
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int Map[20][20], n, w, h, Min = 2e9;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
void destruction(int r, int c, int (*m)[20])
{
    int k = m[r][c];
 
    m[r][c] = 0;
 
    for (int i = 0; i < k; i++)
        for (int d = 0; d < 4; d++)
        {
            int y = r + dy[d] * i;
            int x = c + dx[d] * i;
 
            if (y < 0 || y >= h || x < 0 || x >= w || m[y][x] == 0) continue;
 
            destruction(y, x, m);
        }
}
 
void update(int (*m)[20])
{
    for (int j = 0; j < w; j++)
        for (int i = h - 1; i >= 0; i--)
            if (m[i][j] != 0)
            {
                int r = i;
 
                while (1)
                {
                    if ((r + 1 < h && m[r + 1][j] != 0) || r + 1 >= h)
                    {
                        swap(m[i][j], m[r][j]);
                        break;
                    }
 
                    ++r;
                }
            }
}
 
int cnt(int(*m)[20])
{
    int ret = 0;
 
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)    
            if (m[i][j] != 0) 
                ++ret;
 
    return ret;
}
 
void simulation(int pos, int m[20][20])
{
    if (pos == n)
    {
        Min = min(Min, cnt(m));
        return;
    }
 
    int temp[20][20];
 
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)    
            temp[i][j] = m[i][j];
 
    for (int j = 0; j < w; j++)
    {
        int y = 0, x = j;
 
        while (y + 1 < h && m[y][j] == 0) ++y;
        // while (y < h && m[y][j] == 0) ++y; 라고 작성하여도 Pass(통과)이다.
 
        destruction(y, j, m);
        update(m);
 
        simulation(pos + 1, m);
 
        for (int r = 0; r < h; r++)
            for (int c = 0; c < w; c++)
                m[r][c] = temp[r][c];
    }
}
 
int main(void)
{
    int t = 0;
 
    scanf("%d", &t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        Min = 2e9;
 
        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]);
            
        simulation(0, Map);
 
        printf("#%d %d\n", tc, Min);
    }
 
    return 0;
}