벽돌깨기_5656

문제 출처 : 벽돌깨기_5656

파라미터 정리

N :구슬을 쏠 수 있는 횟수 (1~4)
W : col 정보, 가로 (2~12)
H : row 정보, 세로 (2~15)
HxW 전체 맵 크기, Map[r][c]은 빈 칸(0) 혹은 벽돌(1~9)로 구성됨
게임의 규칙{
구슬은 항상 맨 위에 있는 벽돌만 깰 수 있음
(%)벽돌은 본인 위치에서 상하좌우 (벽돌 숫자-1)만큼의 범위를 가짐
범위 내에 있는 벽돌은 동시에 제거됨
연쇄작용으로 인해 구슬은 제거되면서 (%)을 수행함
빈 공간이 발생할 경우 벽돌은 밑으로 떨어짐
}
원하는 것 = 게임 시뮬레이션 후 최대한 많은 벽돌을 제거했을 때 남은 벽돌의 개수를 출력

간략한 과정

input_1 테스트 케이스 T 입력 받기
input_2_1 N,W,H 입력 받기
input_2_2 초기 맵 정보 Map[15][12]를 입력받음
재귀호출 함수를 이용해서 모든 경우의 수 (= W^N) 구현하기
한 세로줄이 모두 빈칸일 경우 그 곳은 벽돌을 깰 수 없으므로 경우에서 배제
DFS 이용해서 벽돌 숫자에 따라 벽돌이 파괴되고 연쇄작용이 일어나는 것까지 구현
빈 칸이 있을 경우 밑으로 떨어뜨리기
깨트린 벽돌의 최댓값 구하기
res = 처음 - 깨트린 벽돌
output "#n" + res 출력하기

코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int T;
int N,W,H;
int Map[5][15][12];
int Dr[4] = {0,0,1,-1};
int Dc[4] = {1,-1,0,0};

void drop(int cnt){
    queue<int> Q;
    for(int j = 0; j < W; j++){
        for(int i = H-1; i >= 0; i--){
            if(Map[cnt][i][j]){
                Q.push(Map[cnt][i][j]);
                Map[cnt][i][j] = 0;
            }
        }
        for(int i = H-1; Q.size(); --i, Q.pop())//i > H-1-q.size
            Map[cnt][i][j] = Q.front();
    }
}

int DFS(int r, int c, int cnt){
    int dis = Map[cnt][r][c];////
    int res = 1;
    Map[cnt][r][c] = 0;
    for(int i = 0; i < dis; i++){
        for(int j = 0; j < 4; j++){
            int nr = r + Dr[j]*i;
            int nc = c + Dc[j]*i;
            if(nr < 0 || nc < 0 || nr > H-1 || nc > W-1 || Map[cnt][nr][nc]==0) continue;
            res += DFS(nr,nc,cnt);
        }
    }
    return res;
}

void cpy (int cnt){
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            Map[cnt][i][j] = Map[cnt-1][i][j];
}

int solve(int cnt){
    if(cnt > N) return 0;
    int res = 0;
    for(int i = 0; i < W; i++){
        cpy(cnt);
        int temp = 0;
        bool flag = true;
        for(int j = 0; j < H; j++){
            if(Map[cnt][j][i]==0) continue;
            flag = false;
            temp = DFS(j,i,cnt);
            break;
        }
        if(flag) continue;
        drop(cnt);
        res = max(res, solve(cnt+1)+temp);
    }
    return res;
}

int main()
{
    cin >> T;
    for(int t = 0; t < T; t++){
        cin >> N >> W >> H;
        int sum = 0;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                cin >> Map[0][i][j];
                sum += Map[0][i][j] ? 1 : 0;
            }
        }
        int res = sum - solve(1);
        cout << "#" << t+1 << " " << res << '\n';
    }

    return 0;
}

시행착오

백업_0604_pm 04:00
dfs 고쳤는데도 오류 발생, 1번 슈팅은 값 잘 나오는데, 2회 이상부터는 null 반환됨

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 98456154

struct loc{
    int r,c,dis;  
};
int T, N, W, H;
int Map[15][12];
int Bsize[12];
int Dr[4] = {0,1,0,-1};
int Dc[4] = {1,0,-1,0};
int res = INF;


int calculate(){
    int sum = 0;
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            if(Map[i][j] > 0) sum++;
            
    return sum;
}

void shoot(int pos){
    //맵 삭제 + 빈칸 없애기+Bsize도 반영시켜야 함
    //처음 맞은 곳 0으로 만들고, 큐에 넣음
    queue<loc> myqueue;
    int idx = H-Bsize[pos];
    int dis = Map[idx][pos]-1;
    Map[idx][pos] = 0;
    Bsize[pos]--;
    myqueue.push({idx,pos,dis});
    
    //연쇄 작용인한 것 처리하기
    do{
        loc curr = myqueue.back();
        myqueue.pop();
        //4방향에 대해서 살펴봄
        for(int i = 0; i < 4; i++){
            int nr = curr.r, nc = curr.c;
            //서비스 범위까지 적용
            for(int j = 0; j < curr.dis; j++){
                nr += Dr[i];
                nc += Dc[i];
                if(Map[nr][nc] == 0) continue;
                int dis = Map[nr][nc]-1;
                Map[nr][nc] = 0;
                Bsize[nc]--;
                if(dis == 0) continue;
                myqueue.push({nr,nc,dis});
            }
        }
    }while(!myqueue.empty());
    //빈칸 생긴 거 없애주기    
    for(int i = 0; i < W; i++){//col
        if(Bsize[i] == 0) continue;
        for(int j = 0; j < Bsize[i]; j++){//블럭 개수
            int lowest = 0;//가장 낮은 빈칸
             for(int k = H-1; k >= 0; k--){//row
                if(Map[k][i] == 0) lowest = max(lowest,k);
                else{
                    if(lowest == 0) continue;
                    else{
                        Map[lowest][i] = Map[k][i];
                        lowest = 0;
                        Map[k][i] = 0;
                        break;
                    }
                }
             }
        }
    }
    return;
}

void solve(int cnt){
    if(cnt>=N){
        res = min(res, calculate());
        return;
    }
    
    int copy[15][12];
    int copyBsize[12];
    for(int i = 0; i < W; i++){
        if(Bsize[i] <= 0) continue;
        //초기 맵 카피 해두기
        memcpy(copy, Map, sizeof(Map));
        memcpy(copyBsize, Bsize, sizeof(Bsize));
        shoot(i);
        solve(cnt+1);
        //개수 최솟값인지 비교
        //맵 복원
        memcpy(Map, copy, sizeof(Map));
        memcpy(Bsize, copyBsize, sizeof(Bsize));
    }
}

int main()
{
    cin >> T;
    for(int t = 0; t < T; t++){
        cin >> N >> W >> H;
        memset(Map, 0, sizeof(Map));
        memset(Bsize,0,sizeof(Bsize));
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                cin >> Map[i][j];
                if(Map[i][j] > 0) Bsize[j]++;
            }
        }
        solve(0);
        cout << "#" << t+1 << " " << res << endl;
    }

    return 0;
}