SWEA5656.md

벽돌깨기

https://swexpertacademy.com/ [5656]

개요

H(<=15)*W(<=12)의 맵에 벽돌들이 가중치를 가지고 있다. 벽돌이 하나 깨지면 상하좌우방향으로 가중치만큼의 벽돌을 깨트린다. 열을 N번 선택하여I(0<I<W) 구슬을 떨어트려 벽돌을 깨트린다. 구슬 N개를 떨어트려 남아있는 벽돌의 최소를 구하는 문제

분석

브루트포스 문제는 경우의 수를 선택하는 방법에 따라 달리 풀 수 있다. 재귀로 가짓수를 만드는 방법과 단순 반복문으로 가짓수를 만드는 방법이 가능하다. 본인은 반복문을 사용하였지만 이 문제를 푸는 최선의 방법은 DFS라고 생각한다. 매번 선택 시 배열을 미리 저장하고return 후 배열을 다시 초기화한다면 배열 갱신에 필요한 시간을 줄일 수 있을 것이다.

알고리즘

1. W개의 열중 N개의 열을 선택한다.(중복 가능)(0W^N-1)->(0000W-1W-1W-1W-1)W진법

2. map을 map2에 복사한다.

3. DFS를 이용하여 벽돌을 깨트린다. (DFS 4방향을 가중치만큼 가며 map2를 0으로 갱신)

4. 빈 공간이 생기면 벽돌을 떨어트린다.(map2 갱신)

5. 2~4 N번 반복.

6. map2에 남은 벽돌의 개수를 센다. min보다 작으면 min 갱신

7. 2~6을 W^N-1번 반복.

소스

#include <stdio.h>
 
int bc(int r, int c, int w, int h)
{
    if (r >= 0 && r < h && c >= 0 && c < w) return 1;
    return 0;
}
int z(int w, int n)
{
    int i, a;
    a = w;
    for (i = 0; i < n-1; i++) w *= a;
    return w;
}
void choja(int **ja, int n, int nn, int w)
{
    int i, j, a;
    for (i = 0; i < nn; i++)
    {
        a = i;
        for (j = n-1; j>=0; j--)
        {
            ja[i][j] = a % w;
            a /= w;
        }
    }
}
 
void gang(int **map2, int c, int h)
{
    int i, *p, po=h-1;
    p = (int*)malloc(sizeof(int)*h);
    for (i = h-1; i >=0 ; i--)
    {
        p[i] = 0;
        if (map2[i][c] != 0) p[po--] = map2[i][c];
    }
    for (i = h-1; i >=0; i--) map2[i][c] = p[i];
    free(p);
}
 
void dfs(int r, int c, int w, int h, int **map2)
{
    int i, imsi;
    if (bc(r, c, w, h) == 0) return;
    imsi = map2[r][c];
    map2[r][c] = 0;
    for (i = 1; i < imsi; i++)
    {
        dfs(r + i, c, w, h, map2);
        dfs(r - i, c, w, h, map2);
        dfs(r, c + i, w, h, map2);
        dfs(r, c - i, w, h, map2);
    }
}
 
int process(int n, int w, int h, int **map)
{
    int i, j, k, l, m, **map2, **ja, nn, ir, ic, sum=0, min;
    min = w*h;
    nn = z(w, n);
    ja = (int**)malloc(sizeof(int*)*nn);
    for (i = 0; i < nn; i++) ja[i] = (int*)malloc(sizeof(int)*n);
    choja(ja, n, nn, w);
 
     
    for (k = 0; k < nn; k++)
    {
        map2 = (int**)malloc(sizeof(int*)*h);
        for (i = 0; i < h; i++)
        {
            map2[i] = (int*)malloc(sizeof(int)*w);
            for (j = 0; j < w; j++)
            {
                map2[i][j] = map[i][j];
            }
        }
 
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < h; j++)
            {
                if (map2[j][ja[k][i]] != 0)
                {
                    dfs(j, ja[k][i], w, h, map2);
                    break;
                }
            }
            for (j = 0; j < w; j++) gang(map2, j, h);
        }
        sum = 0;
        for (i = 0; i < h; i++)
        {
            for (j = 0; j < w; j++)
            {
                if (map2[i][j] != 0) sum++;
            }
        }
        if (min > sum) min = sum;
        for (i = 0; i < h; i++) free(map2[i]);
        free(map2);
    }
    return min;
}
 
int main()
{
    int T, N, W, H, i, j, k, **map, *answer;
    scanf("%d", &T);
    answer = (int*)malloc(sizeof(int)*T);
    for (i = 0; i < T; i++)
    {
        scanf("%d%d%d", &N, &W, &H);
        map = (int**)malloc(sizeof(int*)*H);
 
        for (j = 0; j < H; j++)
        {
            map[j] = (int*)malloc(sizeof(int)*W);
            for(k = 0; k < W; k++) scanf("%d", &map[j][k]);
        }
 
        answer[i] = process(N, W, H, map);
 
        for (j = 0; j < H; j++) free(map[j]);
        free(map);
    }
    for (i = 0; i < T; i++) printf("#%d %d\n", i + 1, answer[i]);
    free(answer);
    return 0;
}