알고리즘38 :: swea_모의시험_벽돌깨기

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    private static int tc;
    private static int bomb;
    private static int width, height;
    private static int[][] map;
    private static int[][] copymap;
    private static int[][] visit; 
    private static int ans = Integer.MAX_VALUE;
    private static boolean range(int x, int y) {
        if (x >= height || x < 0 || y >= width || y < 0)
            return false;
        else
            return true;
    }
 
    private static void DFSbomb(int x, int y, int range) {
 
        visit[x][y] = 1;
        if (map[x][y] == 1) {
            map[x][y] = 0;
        } else if (map[x][y] == 0) {
            ;
        } else if (map[x][y] >= 1) {
            // 상
            int up = 1;
            int upx = x;
            int tempx = upx;
            while (up < map[tempx][y] && range(upx, y) ) {
                upx -= 1;
                if (range(upx, y) && visit[upx][y] == 0) {
                    DFSbomb(upx, y, map[upx][y]);
                    up += 1;
                }else
                    up+=1;
            } // expect : 위로 올라가면서 1보다 값이 크면 상을 또 볼것이다.
 
            // 하
            int down = 1;
            int downx = x;
            tempx = downx;
            while (down < map[tempx][y] && range(downx, y) ) {
                downx += 1;
                if (range(downx, y) && visit[downx][y]==0) {
                    DFSbomb(downx, y, map[downx][y]);
                    down += 1;
                }else
                    down+=1;
            }
 
            // 좌
            int left = 1;
            int lefty = y;
            int tempy = lefty;
            while (left < map[x][tempy] && range(x, lefty)) {
                lefty -= 1;
                if (range(x, lefty) && visit[x][lefty]==0) {
                    DFSbomb(x, lefty, map[x][lefty]);
                    left += 1;
                }else
                    left+=1;
            }
 
            // 우
            int right = 1;
            int righty = y;
            tempy = righty;
            while (right < map[x][tempy] && range(x, righty)) {
                righty += 1;
                if (range(x, righty) && visit[x][righty]==0) {
                    DFSbomb(x, righty, map[x][righty]);
                    right += 1;
                }else
                    right+=1;
            }
             
            map[x][y] = 0;
        }
    }
 
    private static void DFS(int[] bombpos, int n) {
        if (n == bomb) {
            // bomb개수 만큼 터트리자.
            for (int i = 0; i < bombpos.length; i++) {
                //if(bombpos[0] == 2 && bombpos[1] == 2 && bombpos[2] ==7  )
                //  System.out.println("debug--");
                //System.out.print(bombpos[i]+" ");
                //System.out.println();
                int x = 0;
                int y = bombpos[i];
                // 폭탄을 놓을 y값 선정
 
                k:while (true) {
                    if(map[x][y]>=1)
                        ;
                    else
                        x+=1;
                    if (range(x, y)) {
                        // 만약에 범위 안이라면
                        if (map[x][y] >= 1) {
                            // 1보다 값이 크다면
                            visit[x][y]=1;
                            // 상,하,좌,우 다 확인한다.
                            // 상
                            int up = 1;
                            int upx = x;
                            while (up < map[x][y] && range(upx, y)) {
                                upx -= 1;
                                if (range(upx, y)) {
                                    DFSbomb(upx, y, map[upx][y]);
                                    up += 1;
                                }
                            } // expect : 위로 올라가면서 1보다 값이 크면 상을 또 볼것이다.
 
                            // 하
                            int down = 1;
                            int downx = x;
                            while (down < map[x][y] && range(downx, y)) {
                                downx += 1;
                                if (range(downx, y)) {
                                    DFSbomb(downx, y, map[downx][y]);
                                    down += 1;
                                }
                            }
 
                            // 좌
                            int left = 1;
                            int lefty = y;
                            while (left < map[x][y] && range(x, lefty)) {
                                lefty -= 1;
                                if (range(x, lefty)) {
                                    DFSbomb(x, lefty, map[x][lefty]);
                                    left += 1;
                                }
                            }
 
                            // 우
                            int right = 1;
                            int righty = y;
                            while (right < map[x][y] && range(x, righty)) {
                                righty += 1;
                                if (range(x, righty)) {
                                    DFSbomb(x, righty, map[x][righty]);
                                    right += 1;
                                }
                            }
                            visit = new int[height][width];
                            map[x][y] = 0;
                            break k;
                        }
                    } else
                        break k; // 범위 벗어났다.
                     
                }
                 
                //수직 낙하!! 
                 
                 
                for (int b = height-1; b >=0; b--) {
                    for (int bb = width-1; bb >=0; bb--) {
                        if(map[b][bb]!=0) {
                            int temp = map[b][bb];
                            int cc = b;
                            cc+=1;
                            while(range(cc,bb) && map[cc][bb]==0) {
                                 
                                map[cc][bb] = temp;
                                map[cc-1][bb] = 0;
                                temp = map[cc][bb];
                                cc+=1;
                            }
                        }
                    }
                } // end of for loop
                int c = 0;
                for (int si = 0; si < height; si++) {
                    for (int j = 0; j < width; j++) {
                        if(map[si][j]>=1)
                            c+=1;
                    }
                     
                } // end of for loop
 
                if(ans>c)
                    ans = c;
                 
            }
 
             
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    map[i][j] = copymap[i][j];
                }
            } // end of for loop
        } else {
            for (int i = 0; i < width; i++) {
                bombpos[n] = i;
                DFS(bombpos, n + 1);
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        for(int sst=1; sst<=tc; sst++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        bomb = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());
        visit = new int[height][width];
         
        map = new int[height][width];
        copymap = new int[height][width];
        for (int i = 0; i < height; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < width; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                copymap[i][j] = map[i][j];
            }
        } // end of for loop
 
        int[] bombpos = new int[bomb];
        DFS(bombpos, 0);
        System.out.println("#"+sst+" "+ans);
        ans = Integer.MAX_VALUE;
        }
    }
 
}

 

1. width 에서 좌표 3개를 선택

2. 위에서 부터 전수 조사해서  map에 저장된 값이 1 이상이라면 (여기서 방문체크 => 없다면 스택오버 플로우)

3. 상, 하, 좌, 우 로 범위를 체크 

4. 한번 폭탄을 터트리고 아래서부터 확인해서 height 범위에서 내려갈 수 있고 0이라면 아래로 밀기

 

완전탐색 + 시뮬레이션 문제