SWEA 5656. [모의 SW 역량테스트] 벽돌깨기 :: 돼지개발자

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

"DFS와 BFS 를 이용한 단순 구현, 깊은 복사"

벽돌이 쌓여있는 격자에서 W의 열 중에 깰 수 있는 벽돌들의 경우를 DFS를 이용하여 탐색한다. BFS를 이용해 선택한 벽돌의 숫자 만큼 상,하,좌,우 벽돌을 탐색하여 해당 턴에 삭제될 벽돌들을 넣고 벽돌을 삭제 시킨다. 그리고 공중에 떠 있는 벽돌들을 아래로 내려준다.

이 과정에서 나는 깊은 복사를 사용했다. 시뮬레이션 중에 백트래킹이 힘들 경우에는 깊은 복사를 사용하는 것도 좋은 방법 인 것 같다. map 의 크기가 작다면 옅은 복사나 깊은 복사나 그렇게 큰 차이가 없다고 한다. 작다는 기준은 얼마 인지는 모르겠다... 감으로..?

아무튼 백트래킹이 힘드므로 깊은 복사를 사용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int T;
    static int N,W,H;
    static Queue<Node> q = new LinkedList<>();
    static int min;
    public static void main(String[] args) throws IOException  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        int t = 1;
        
        while(T-- > 0) {
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            
            int[][] map = new int[H][W];
            min = Integer.MAX_VALUE;
            
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < W; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            solve(map,0);
            System.out.printf("#%d %d%n",t++,min == Integer.MAX_VALUE ? 0: min);
        }
    }
    
    static void solve(int[][] map, int cnt ) {
        
        if(cnt == N) {
            int sum = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if(map[i][j] != 0) sum++;
                }
            }
            min = Math.min(min,sum);
            
            return;
        }
        
        for (int i = 0; i < W; i++) {
            int j = 0;
            
            while(j < H) {
                if(map[j][i] != 0) break;
                j++;
            }
            if(j == H) continue;
            
            int[][] arr = copy(map);
            q.add(new Node(j, i));
            crush(arr);
            solve(arr,cnt+1);
        }
        
    }
    
    static void crush(int[][] map) {
        while(!q.isEmpty()) {
            Node cur = q.poll();
            int range = map[cur.x][cur.y]-1;
            map[cur.x][cur.y] = 0;
            
            for (int i = cur.x-range < 0 ? 0 : cur.x-range ; i <= (cur.x+range >= H ? H-1 : cur.x+range); i++) {
                if(map[i][cur.y] == 0) continue;
                
                if(map[i][cur.y] == 1) {
                    map[i][cur.y] = 0;
                }
                else {
                    q.add(new Node(i, cur.y));
                }
            }
            
            for (int i = cur.y-range < 0 ? 0 : cur.y-range ; i <= (cur.y+range >= W ? W-1 : cur.y+range); i++) {
                if(map[cur.x][i] == 0) continue;
                
                if(map[cur.x][i] == 1) {
                    map[cur.x][i] = 0;
                }
                else {
                    q.add(new Node(cur.x, i));
                }
            }
        }
        
        // arrange
        for (int i = H-2; i >= 0; i--) {
            for (int j = 0; j < W; j++) {
                if(map[i][j] == 0) continue;
                
                int range = map[i][j];
                int temp = i;
                map[i][j] = 0;
                
                while(true) {
                    if(temp+1 >= H || map[temp+1][j] != 0) break;
                    temp++;
                }
                map[temp][j] = range;
            } 
        }
        
    }
    
    static int[][] copy(int[][] map) {
        int[][] temp = new int[H][W];
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                temp[i][j] = map[i][j];
            }
        }
        return temp;
    }
    
}
 
class Node {
    int x;
    int y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}