<Algorithm> 163. 벽돌깨기(SWExpert)

1. 벽돌깨기(SWExpert)

   사용 알고리즘 :  DFS, 완전탐색

• 이 문제를 풀면서 벽돌의 크기만큼 깼을때 다시 돌아오는 경우를 어떻게 처리 해야할지가 가장 어려웠다. 

• 예를 들어 왼쪽으로 깨질때 3 0 8 이면 8이 깨질때 다시 왼쪽으로 가야하는 부분에서 감이 잘안와서 다른포스팅을 참고했다. 

• 위에 저문제를 벽돌크기만큼 반복해서 처리하는 것을 보고 감탄했다. 좀 더 넓게 보는 사고가 필요한 것 같다.

문제에 대한 접근&생각

1. 공은 N번 쏠수 있고 쏜데 또 쏠수 있음 -> 완전탐색!
2. 벽돌이 깨질떄 상하좌우에 있는 벽돌도 깨짐 -> DFS!
3. 벽돌에는 크기가 있어서 크기만큼 깨져야함 -> DFS 반복!

다른 방법 풀이

• 깨지는 벽돌의 수를 DP를 통해 저장하여 마지막에 총개수에서 빼주는 방식

내 코드 

import java.util.Scanner;
 
public class Solution {
    static int n;
    static int w;
    static int h;
    static int[][] map;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        for(int t = 1; t <= test; t++ ) {
            /******************************
             * 벽돌을 N번 쏘는 위치를 완전탐색한다.
             * 그리고 DFS를 이용하여 해당 벽돌의
             * 크기 만큼 반복을 하여 상하좌우
             * 를 벽돌크기만큼 없애주고 한번 쏘고 난후에
             * 정렬해주고 다시쏘는 것을 반복하여
             * 남은 벽돌의 최솟값을 구한다.
             *******************************/
            n = sc.nextInt(); w = sc.nextInt(); h = sc.nextInt();
            map = new int[h][w];
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    int temp = sc.nextInt();
                    if(temp != 0) {
                        map[i][j] = temp;
                    }
                }
            }
            res = Integer.MAX_VALUE;
            solve(0);
            System.out.println("#"+t+" "+res);
        }
    }
    static int res;
    private static void solve(int deep) {
        //벽돌위치 완전탐색 
        
        int[][] temp_map = new int[h][w];
        deepClone(map, temp_map);
        
        if(n==deep) {
            int cnt = 0;
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    if(map[i][j] != 0) cnt++; 
                }
            }
            res = Math.min(res, cnt);
            return;
        }        
        
        for(int i = 0; i < w; i++) {
            for(int j = 0; j < h; j++) {
                if(map[j][i] != 0) {
                    dfs(j, i);
                    break;
                }
            }
            pullDown();
            solve(deep+1);
            deepClone(temp_map, map);
        }
    }
    private static void dfs(int x,int y) {
        int range = map[x][y];
        map[x][y] = 0;
        
        for(int i = 0; i < 4; i++) {
          for(int size = 0; size < range; size++) {
              // 벽돌 크기만큼 dfs 반복
                int nx = x + dx[i]*size;
                int ny = y + dy[i]*size; 
                if(isBoundary(nx, ny)&&map[nx][ny] != 0) { 
                    dfs(nx, ny);
                }
            }
        }
        
    }
    
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    public static boolean isBoundary(int nx,int ny) {
        if(nx < 0 || ny < 0 || nx >= h || ny >= w)
            return false;
        return true;
    }
    
    private static void pullDown() {
        // 중력
        for(int i = 0; i < w; i++) {
            for(int j = h-1; j >= 1; j--) {
                for(int p = j-1; p >= 0;p--) {
                    if(map[j][i]!=0) 
                        break;
                    if(map[p][i]!=0) {
                        map[j][i] = map[p][i];
                        map[p][i] = 0; 
                        break;
                    }
                }
            }
        }
        
    }
    public static void deepClone(int[][] origin,int[][] copy) {
        for(int i = 0; i < h; i++) {
            copy[i] = origin[i].clone();
        }
    }
    
}
 

 

얻은 것

• 참조 변수를 백트래킹 할 경우는 지역변수를 이용한다.!

참고 & 출처  

https://charm-charm.postype.com/post/3202843