[SWEA] 5656 : [모의 SW 역량테스트] 벽돌 깨기

문제 >> 5656 : [모의 SW 역량테스트] 벽돌 깨기

1. 구슬 쏠 곳 선택하기

rperm() : 중복순열 이용 

2. 벽돌 깨트리기

brick() : bfs 이용

3. 벽돌 밑으로 당기기

removeEmpty() : Queue 이용

큐에 0이 아닌 값을 다 옮긴 후 밑부터 다시  삽입.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
//SWEA :: 5656 [모의 SW 역량테스트] 벽돌 깨기
//2019-03-07
public class Solution5656 {
    static int[][] origin_map;
    static int[][] map;
    static int[] set;
    static int[] origin_top;
    static int[] top;
    static HashSet<Integer> hs;
    static int N, W, H;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
    static int min;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
            N = Integer.parseInt(st.nextToken()); // 벽돌 개수
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            min = Integer.MAX_VALUE;
            origin_map = new int[H][W];
            map = new int[H][W];
            set = new int[N]; // 벽돌을 떨어트릴 idx를 저장하는 배열
            hs = new HashSet<Integer>();
            
            // 벽돌의 높이를 저장하는 배열 : W번째 벽돌의 높이는 top[W];
            origin_top = new int[W];
 
            Arrays.fill(origin_top, -1);
 
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(bf.readLine(), " ");
                
                //i번째 줄의 벽돌의 최고높이 좌표 == (top[j],j)
                //벽돌이 있고, top[i] == -1 (아직 비어있으면 ) top을 갱신해준다.
                for (int j = 0; j < W; j++) {
                    origin_map[i][j] = Integer.parseInt(st.nextToken());
                    if (origin_map[i][j] != 0 && origin_top[j] == -1) {
                        origin_top[j] = i;
                    }
                }
            } // input
 
            rperm(0);
            
            System.out.println("#"+tc+" "+min);
        } // end of tc
    }// end of main
 
    public static void mapcopy() {
        map = new int[H][W];
        top = new int[W];
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                map[i][j] = origin_map[i][j];
            }
        }
        
        for(int i=0;i<W;i++) {
            top[i] = origin_top[i];
        }
    }
 
    // wCn 수행 , 벽돌을 떨어트릴 곳을 결정한다.
    public static void rperm(int len) {
        if (len == N) { // N개의 중복 순열이 완료되었을 때 --> set 배열에 저장되있음.
            mapcopy(); 
            for (int j = 0; j < N; j++) {
                // 벽돌을 떨어트릴 좌표 (y,x)
                if(top[set[j]]==-1||top[set[j]]>H-1) continue;
                brick(top[set[j]], set[j]);
                removeEmpty();
            }
            
            int cnt = 0;
            for(int i=0;i<H;i++) {
                for(int j=0;j<W;j++) {
                    if(map[i][j]!=0) cnt++;
                }
            }
            min = min > cnt ? cnt : min;
            
            return;
        }
 
        for (int i = 0; i < W; i++) {
            set[len] = i;
            rperm(len + 1);
        }
    }
 
    // x위치에 벽돌을 떨어트린다.
    public static void brick(int y, int x) {
        Queue<pair> q = new LinkedList<>();
        q.add(new pair(y, x));
        while (!q.isEmpty()) {
            pair p = q.poll();
            int py = p.y;
            int px = p.x;
            int pw = map[py][px];
 
            map[py][px] = 0; // 벽돌 깨기
            hs.add(px); // 빈공간 제거를 위해 x좌표 저장
 
            if (pw == 1) continue;
 
            for (int i = 0; i < 4; i++) {
                int ny = py;
                int nx = px;
                for (int j = 0; j < pw - 1; j++) {
                    ny += dy[i];
                    nx += dx[i];
                    if (ny < 0 || ny > H - 1 || nx < 0 || nx > W - 1 || map[ny][nx] == 0)
                        continue;
                    q.add(new pair(ny, nx));
                }
            }
        }
    } // end of brick
 
    public static void removeEmpty() {
        Queue<Integer> tmpQ = new LinkedList<Integer>();
        Iterator<Integer> it = hs.iterator();
        while (it.hasNext()) {
            int xIdx = it.next(); // 확인해야 할 x index
 
            for (int i = H - 1; i >= top[xIdx]; i--) {
                if (map[i][xIdx] != 0)
                    tmpQ.add(map[i][xIdx]);
                    map[i][xIdx]=0;
            }
            int tmpSize = tmpQ.size();
            top[xIdx] = H - tmpSize; // 벽돌을 밑으로 땡긴 후 최상위 좌표.
            for (int i = 0; i < tmpSize; i++) {
                map[H - 1-i][xIdx] = tmpQ.poll();
            }
        }
        hs.clear();
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
}