SWEA5656 [모의 SW 역량테스트] 벽돌 깨기 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE&problemTitle=모의&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA5656.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA5656
//
//  Created by Hwayeon on 2021/10/17.
//

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int N, W, H;
int brick[16][13] = {0, };
int copy_brick[16][13] = {0, };
int visit[16][13] = {0, };
vector<int> order;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int answer = 181;

void break_bricks(int sx, int sy){
    memset(visit, 0, sizeof(visit));
    queue<pair<int, int>> q;
    q.push({sx, sy});
    visit[sy][sx] = 1;
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        int num = copy_brick[now_y][now_x];
        copy_brick[now_y][now_x] = 0;
        q.pop();
        for(int d=0; d<4; d++){
            for(int i=1; i<num; i++){
                int nx = now_x + i*dx[d];
                int ny = now_y + i*dy[d];
                if(nx<0 || nx>=W || ny<0 || ny>=H) continue;
                if(visit[ny][nx]) continue;
                if(copy_brick[ny][nx] == 0) continue;
                q.push({nx, ny});
                visit[ny][nx] = 1;
            }
        }
    }
}

void fall_down_bricks(){
    for(int x=0; x<W; x++){
        for(int y=H-1; y>=0; y--){
            if(copy_brick[y][x] == 0){
                int yy;
                bool check = false;
                for(yy=y-1; yy>=0; yy--){
                    if(copy_brick[yy][x] > 0) {
                        check = true;
                        break;
                    }
                }
                if(!check) break;
                copy_brick[y][x] = copy_brick[yy][x];
                copy_brick[yy][x] = 0;
            }
        }
    }
}

void count_bricks(){
    int cnt = 0;
    for(int y=0; y<H; y++){
        for(int x=0; x<W; x++){
            if(copy_brick[y][x] > 0) cnt++;
        }
    }
    if(cnt < answer) answer = cnt;
}

void shoot_bead(){
    memcpy(copy_brick, brick, sizeof(brick));
    for(int i=0; i<order.size(); i++){
        int x = order[i];
        int y;
        for(y=0; y<H; y++){
            if(copy_brick[y][x] > 0) break;
        }
        if(y == H-1 && copy_brick[y][x] == 0) return;
        break_bricks(x, y);
        fall_down_bricks();
    }
    count_bricks();
}

void choose_bead(int cnt){
    if(cnt == N){
        shoot_bead();
        return;
    }
    for(int x=0; x<W; x++){
        order.push_back(x);
        choose_bead(cnt+1);
        order.pop_back();
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        answer = 181;
        cin >> N >> W >> H;
        for(int y=0; y<H; y++){
            for(int x=0; x<W; x++){
                cin >> brick[y][x];
            }
        }
        choose_bead(0);
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}

---

풀이 과정

풀이 시간 1시간 22분

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int N, W, H;

//원래 벽돌 상태를 저장할 배열
int brick[16][13] = {0, };

//벽돌 깨트리기 시뮬레이션 할 배열
int copy_brick[16][13] = {0, };
int visit[16][13] = {0, };

//N개의 깨트릴 벽돌 순서를 담는 벡터
vector<int> order;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int answer = 181;

void break_bricks(int sx, int sy){
    memset(visit, 0, sizeof(visit));
    queue<pair<int, int>> q;
    //깨트릴 벽돌 추가
    q.push({sx, sy});
    visit[sy][sx] = 1;
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        //깨트릴 벽돌의 숫자를 num에 담고, 벽돌을 깨트린다
        int num = copy_brick[now_y][now_x];
        copy_brick[now_y][now_x] = 0;
        q.pop();
        //깨트렸던 벽돌의 숫자-1이내에 있는 벽돌을 탐색한다(좌,상,우,하 4방향)
        for(int d=0; d<4; d++){
            for(int i=1; i<num; i++){
                int nx = now_x + i*dx[d];
                int ny = now_y + i*dy[d];
                
                //범위를 벗어난 경우, 무시한다
                if(nx<0 || nx>=W || ny<0 || ny>=H) continue;
                //이미 이전에 탐색한 벽돌인 경우, 무시한다
                if(visit[ny][nx]) continue;
                //벽돌이 없는 경우, 무시한다
                if(copy_brick[ny][nx] == 0) continue;
                
                //깨트릴 벽돌이 있는 경우 큐에 추가하고 방문 처리한다
                q.push({nx, ny});
                visit[ny][nx] = 1;
            }
        }
    }
}

void fall_down_bricks(){
	//각 열에 대해서
    for(int x=0; x<W; x++){
    	//마지막 행부터 가장 윗 행까지 차례대로 탐색
        for(int y=H-1; y>=0; y--){
        	//해당 칸에 벽돌이 비어있는 경우,
            if(copy_brick[y][x] == 0){
                int yy;
                //check = true -> 위에 떨어질 벽돌이 있는 경우, check = false -> 위에 떨어질 벽돌이 없는 경우
                bool check = false;
                for(yy=y-1; yy>=0; yy--){
                    if(copy_brick[yy][x] > 0) {
                        check = true;
                        break;
                    }
                }
                //더이상 해당 열에 떨어지는 벽돌이 없는 경우, 다음 열을 탐색한다
                if(!check) break;
                
                //떨어뜨릴 벽돌이 있는 경우, 벽돌을 떨어뜨린다
                copy_brick[y][x] = copy_brick[yy][x];
                copy_brick[yy][x] = 0;
            }
        }
    }
}

void count_bricks(){
    int cnt = 0;
    for(int y=0; y<H; y++){
        for(int x=0; x<W; x++){
        	//해당 칸에 벽돌이 있는 경우, 카운팅
            if(copy_brick[y][x] > 0) cnt++;
        }
    }
    //가장 적은 남은 벽돌의 개수로 cnt 갱신
    if(cnt < answer) answer = cnt;
}

void shoot_bead(){
	//copy_brick을 원래 벽돌 상태로 초기화 한다
    memcpy(copy_brick, brick, sizeof(brick));
    
    for(int i=0; i<order.size(); i++){
    	//깨트릴 벽돌을 찾는다
        int x = order[i];
        int y;
        for(y=0; y<H; y++){
            if(copy_brick[y][x] > 0) break;
        }
        //x열에 벽돌이 없는 경우, 해당 order은 무효이므로 함수 종료
        if(y == H-1 && copy_brick[y][x] == 0) return;
        
        //벽돌을 깨트린다 -> O(W*H)
        break_bricks(x, y);
        
        //벽돌을 떨어뜨린다 -> O(W*H)
        fall_down_bricks();
    }
    //N개의 벽돌을 모두 깨트렸으므로, 남은 벽돌의 개수를 구한다 -> O(W*H)
    count_bricks();
}

void choose_bead(int cnt){
	//깨트릴 N개의 벽돌 순서를 다 고른 경우,
    if(cnt == N){
    	//order에 담긴 순서대로 벽돌 깨트리기 시뮬레이션을 진행한다 -> O(N*W*H)
        shoot_bead();
        return;
    }
    
    //깨트릴 벽돌을 고른다
    for(int x=0; x<W; x++){
        order.push_back(x);
        choose_bead(cnt+1);
        order.pop_back();
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        answer = 181;
        cin >> N >> W >> H;
        for(int y=0; y<H; y++){
            for(int x=0; x<W; x++){
                cin >> brick[y][x];
            }
        }
        //N개의 벽돌을 깨트리는 순서의 모든 경우의 수 구하기
        choose_bead(0);
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}
//시간복잡도 = O(N^2*W^2*H), 공간복잡도 = O(W*H)