ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #5656 _ 벽돌 깨기
    Problem Solving/SWEA 2019. 8. 4. 10:28
    728x90

    [벽돌 깨기] https://swexpertacademy.com/main/code/problem/problemDetail.do

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

     

    벡터를 사용하여 벽돌을 세로가 아닌 가로로 저장하고, 가장 끝에 있는 값을 깨는 방법으로 구현하였다.

    (erase를 사용하여 가운데 값을 삭제해도 앞으로 땡기는 작업을 하지 않기 위해 벡터 사용)

    하지만, 직관적으로 보기에는 배열을 이용하는게 좋은 것 같다..;;

     

    깰 수 있는 모든 경우의 수를 다 돌려 가장 벽돌이 적게 남은 경우를 출력하였다.

    모든 경우의 수를 하지 않는 방법을 생각하다가,,,

    제한 시간이 3초인 것을 보고 모든 경우의 수를 다 돌려보기로 결정하였다.

     

    벽돌을 제거할 때, 상하좌우로 제거되기 때문에 bfs를 이용하였다.

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #define MAX_W 12
    #define MAX_H 15
    
    using namespace std;
    vector<vector<int> > tmp_map, map;
    int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
    int n, w, h;
    int remain, bp = 0;
    
    int solve(int count, int block_loc[]);
    void break_bfs(pair<int, int> x_y);
    int count_block();
    int main() {
    	int test_case, tmp;
    
    	scanf("%d", &test_case);
    	for (int k = 1; k <= test_case; k++) {
    		int loc[5] = { 0, };
    		map = vector<vector<int> >(MAX_W + 1, vector<int>(MAX_H + 1, 0));
    		remain = 999999;
    		bp = 0;
    
    		scanf("%d %d %d", &n, &w, &h);
    		for (int i = 0; i < h; i++) {
    			for (int j = 0; j < w; j++) {
    				scanf("%d", &tmp);
    				map[j].insert(map[j].begin(), tmp);
    			}
    		}
    
    		solve(0, loc);
    		printf("#%d %d\n", k, remain);
    	}
    
    	return 0;
    }
    
    int solve(int count, int block_loc[]) {
    	if (bp == 1) return 0;
    	if (count == n) {
    		tmp_map.clear();
    		tmp_map.assign(map.begin(), map.end());
    		for (int i = 0; i < n; i++) {
    			int x = block_loc[i];
    			int y = find(tmp_map[x].begin(), tmp_map[x].end(), 0) - tmp_map[x].begin() - 1;
    			if (y < 0) break;
    			break_bfs(make_pair(x, y));
    		}
    		remain = min(remain, count_block());
    		if (remain == 0) bp = 1;
    		return 0;
    	}
    	for (int i = 0; i < w; i++) {
    		block_loc[count] = i;
    		solve(count + 1, block_loc);
    	}
    
    	return 0;
    }
    
    void break_bfs(pair<int, int> x_y) {
    	queue<pair<int, int> > q;
    	queue<int> range;
    	priority_queue<pair<int, int> > del;
    	pair<int, int> tmp;
    	int x, y, break_size;
    
    	q.push(x_y);
    	range.push(tmp_map[x_y.first][x_y.second]);
    	tmp_map[x_y.first][x_y.second] = 0;
    	del.push(make_pair(x_y.first, x_y.second));
    
    	while (!q.empty()) {
    		tmp = q.front();
    		break_size = range.front();
    		q.pop();
    		range.pop();
    
    		for (int i = 1; i < break_size; i++) {
    			for (int j = 0; j < 4; j++) {
    				x = tmp.first + (dx[j] * i);
    				y = tmp.second + (dy[j] * i);
    				if (x < 0 || y < 0 || x >= w || y >= h) continue;
    				if (tmp_map[x][y] == 0) continue;
    				if (tmp_map[x][y] > 1) {
    					q.push(make_pair(x, y));
    					range.push(tmp_map[x][y]);
    				}
    				tmp_map[x][y] = 0;
    				del.push(make_pair(x, y));
    			}
    		}
    	}
    
    	while (!del.empty()) {
    		tmp = del.top();
    		del.pop();
    		tmp_map[tmp.first].erase(tmp_map[tmp.first].begin() + tmp.second);
    	}
    }
    
    int count_block() {
    	int count = 0;
    
    	for (int i = 0; i < w; i++) {
    		for (int j = 0; j < h; j++) {
    			if (tmp_map[i][j] == 0) break;
    			count++;
    		}
    	}
    
    	return count;
    }
    반응형

    'Problem Solving > SWEA' 카테고리의 다른 글

    [SWEA] #1210 _ Ladder1  (0) 2019.08.28
    [SWEA] #1209 _ Sum  (0) 2019.08.12
    [SWEA] #5656 _ 벽돌 깨기  (0) 2019.08.04
    [SWEA] #5644 _ 무선 충전  (0) 2019.08.04
    [SWEA] #5215 _ 햄버거 다이어트  (0) 2019.08.04
    [SWEA] #2805 _ 농작물 수확하기  (0) 2019.08.04

    댓글 0

@Jo Grini's Blog