[SWEA] 5656. 벽돌 깨기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

SW Expert Academy

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
	
	static int T, N, W, H, answer;
	static int[] temp;
	static int[][] arr, map;
	static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		T = sc.nextInt();
		
		for(int i=0; i<T; i++) {
			N = sc.nextInt();
			H = sc.nextInt();
			W = sc.nextInt();
			temp = new int[N];
			arr = new int[W][H];
			map = new int[W][H];

			for(int j=0; j<W; j++) {
				for(int k=0; k<H; k++) {
					arr[j][k] = sc.nextInt();
				}
			}
			
			answer=Integer.MAX_VALUE;
			
			for(int j=0; j<H; j++) {
				temp[0] = j;
				combination(j, 0);
			}
			
			System.out.println("#" + (i+1) + " " + answer);
		}
	}
	
	public static void combination(int start, int depth) {
		if(depth == N-1) {
			copy();
			for(int i=0; i<N; i++) {
				drop(temp[i]);
				fall();
			}
			
			answer = Math.min(answer, calc());
			
			return;
		}
		
		for(int i=0; i<H; i++) {
			temp[depth+1] = i;
			combination(i, depth+1);
		}
	}
	
	public static void fall() {
		int[][] a = new int[W][H];
		
		int row = W-1;
		
		for(int i=0; i<H; i++) {
			row = W-1;
			Stack<Integer> s = new Stack<Integer>();
			for(int j=0; j<W; j++) {
				if(map[j][i] != 0) s.add(map[j][i]);
			}
			while(!s.isEmpty()) {
				a[row--][i] = s.pop();
			}
		}
		
		for(int i=0; i<W; i++) {
			for(int j=0; j<H; j++) {
				map[i][j] = a[i][j];
			}
		}
	}
	
	public static int calc() {
		int sum = 0;
		for(int i=0; i<W; i++) {
			for(int j=0; j<H; j++) {
				if(map[i][j] != 0) sum++; 
			}
		}
		return sum;
	}
	
	public static void drop(int col) {
		for(int i=0; i<W; i++) {
			if(map[i][col] > 0) {
				bomb(new Dot(i, col));
				break;
			}
		}
	}
	
	public static void bomb(Dot d) {
		Queue<Dot> queue = new LinkedList<Dot>();
		queue.offer(new Dot(d.x, d.y));
		
		while(!queue.isEmpty()) {
			Dot dot = queue.poll();
			int temp = map[dot.x][dot.y];
			map[dot.x][dot.y] = 0;
			for(int i=0; i<4; i++) {
				for(int j=0; j<temp; j++) {
					int nx = dot.x+(dir[i][0]*j);
					int ny = dot.y+(dir[i][1]*j);
					
					if(isInside(nx, ny) && map[nx][ny] > 0) {
						queue.offer(new Dot(nx, ny));
					}
				}
			}
		}
	}
	
	public static boolean isInside(int x, int y) {
		if(x>=0 && x < W && y>=0 && y<H) return true;
		else return false;
	}
	
	public static void copy() {
		for(int i=0; i<W; i++) {
			for(int j=0; j<H; j++) {
				map[i][j] = arr[i][j];
			}
		}
	}
	
	public static void print() {
		for(int i=0; i<W; i++) {
			for(int j=0; j<H; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}

class Dot {
	int x;
	int y;
	Dot(int x, int y){
		this.x=x;
		this.y=y;
	}
}

---

최근에 제가 풀었던 가장 어려운 문제였습니다. 풀다가 포기하고 다른 블로그를 참고하여 풀었는데 브루트포스, DFS, BFS 종합적인 개념을 포함하는 문제인 것 같습니다. 어려웠던 점은 구슬을 W x H 배열에 N번 떨어뜨리는데 1번째 부터 H번째 까지 떨어뜨릴 수 있는 모든 경우의 수를 뽑는것과 구슬을 떨어뜨렸을 때 벽돌마다 숫자가 적혀있는데 구술이 명중한 벽돌을 상하좌우로 벽돌에 적힌 숫자-1만큼 제거시키는 것이었습니다. 여기서 끝나는게 아니라 벽돌을 제거하고 다시 빈공간을 위에서부터 땡겨와서 벽돌을 채워야 하는데 그 부분을 코딩하는 것도 쉽지 않았습니다. 구슬을 떨어뜨리는 경우의 수를 뽑는것은 제가 얼마전에 풀었던 감시(https://daily-life-of-bsh.tistory.com/121) 에서 CCTV 를 돌리는 것처럼 구현하였고, 벽돌을 상하좌우 제거하는 것은 BFS 방식으로 한다는 것을 다른 블로그를 통해서 해결했습니다. 그리고 벽돌을 제거하고 빈공간을 채우는 것은 stack에 저장하여 후입선출 방식으로 2차원 배열에 채웠습니다.

[ 문제 풀이 ]

1. arr 에 처음 주어진 2차원 배열을 저장하고 map 에는 copy() 함수를 이용해서 매 연산마다 arr에 있는 2차원 배열을 모두 복사하여 map 에서 구슬이 떨어진 벽돌들을 제거합니다.

2. temp 에는 구슬이 N 번 떨어지는 y 좌표를 저장하는데 만약에 N=3, H=9 이면 000, 001, 002, ... , 009, 100, 101, 102, 103, ... , 109, ... , 999 까지 구슬이 3번 떨어질 y좌표들의 모든 조합을 뽑아서 temp에 저장합니다.

3. temp 에 떨어질 y좌표가 저장되면 drop() 함수를 이용해서 구슬을 떨어뜨리고 bomb() 함수를 이용해서 벽돌에 적혀있는 수-1만큼 제거시킵니다. 여기에서 저는 BFS로 2중 for문을 사용하여 벽돌을 제거하였는데 바깥쪽 for문은 동서남북 네방향을 나타내는 반복문이고 안쪽 for문은 벽돌에 적인 숫자를 temp에 저장하여 temp의 크기만큼 동서남북방향의 벽돌을 제거하는 방식으로 구현했습니다. 이 부분은 다른 블로그를 참고하여 구현하였는데 많이 사용되는 방식이기 때문에 숙지해둬야 할 것 같습니다.

4. drop() 함수가 한번 실행될 때마다 제거된 벽돌이 map에 저장되어 있고 빈공간을 위에서부터 땡겨와 채워야하기 때문에 fall() 함수를 실행합니다.

5. fall() 함수는 각 열마다 처음부터 마지막 행까지 확인하면서 0이아니라면 stack에 넣은 후에 끝에서부터 stack에서 pop을 해서 채워넣는 함수입니다. 여기에서 주의할 점은 fall() 함수는 새로운 2차원 a배열을 만들어서 수행하고 마지막에 a함수를 map함수에 복사해줘야 한다는 점입니다. 왜냐하면 map 배열에서만 위의 연산을 수행하게 되면 stack에 열마다 벽돌을 넣었을 때 map의 열을 초기화시키고 복사해줘야하는 점이 번거롭기 때문입니다.

6. 한번의 벽돌 N 번 떨어뜨리기가 끝나면 calc() 함수를 이용해서 남은 벽돌의 개수의 최솟값을 구합니다.