[SWEA] 벽돌깨기

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

SW Expert Academy

 

후기

오랜만에 푸는 구현문제라 신경쓸 부분이 많아서 피곤했지만

입력값이 작고 예외가 적어서 다른 부분을 고려하지 않고 완전탐색으로 풀 수 있는 문제였다.

 

 

풀이 방법

문제 유형 : DFS or BFS + 구현

 

• 백트래킹으로 map을 복사해서 넘겨주면서 구슬 쏘기
  • N번 구슬을 쏘면 남아있는 벽돌 개수를 세서 min과 비교
• 위에서부터 떨어뜨려서 0이 아닌 벽돌이 나오면 부수기 (crush)
• 자기자신과 벽돌값-1만큼 상하좌우 부수기
  • 만약 부수다가 1보다 큰 벽돌이 나오면 crush 재귀
• 벽돌 내리기
  • 위에서부터 0보다 큰 블럭을 스택에 넣은 후
  • 밑에서부터 스택이 빌때까지 pop

 

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution_5656_벽돌깨기 {

	public static void main(String[] args) throws Exception 

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T=Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++) {
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			
			map = new int[H][W];
			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());
				}
			}
			
			min = Integer.MAX_VALUE;
			dfs(0, map);
			
			System.out.println("#"+test_case+" "+min);
			
		}

	}
	

	static int N, W, H;
	static int min = Integer.MAX_VALUE;
	static int[][] map;
	static int[][] delta = {{0,1},{0,-1},{1,0},{-1,0}};
	
	static void dfs(int cnt, int[][] map) {
		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 c=0; c<W; c++) {
			//map 복사
			int[][] newMap = new int[H][W];
			for(int i=0; i<H; i++) {
				newMap[i] = map[i].clone();
			}
			game(c, newMap);
			dfs(cnt+1, newMap);
		}
	}
	
	static void game(int c, int[][] map) {
		int r = 0;
		//벽돌이 나올때까지 아래로
		while(checkRange(r,c) && map[r][c]==0) r++;
		//벽돌이 있을때만 부수기
		if(r<H){ 
			crush(r,c, map);
			down(map);
		}
	}
	
	static void crush(int r, int c, int[][] map) {
		int cnt = map[r][c];
		map[r][c] = 0;
		for(int[] d : delta) {
			int tr = r;
			int tc = c;
			for(int i=0; i<cnt-1; i++) {
				tr += d[0];
				tc += d[1];
				if(checkRange(tr,tc)) {
					if(map[tr][tc]>0) {
						//1보다 큰 값의 벽돌이 나오면 crush 재귀
						if(map[tr][tc]>1) crush(tr,tc,map);
						else map[tr][tc]=0;
					}
				}
				else break;
			}
		}
	}
	
	static void down(int[][] map) {
		for(int c=0; c<W; c++) {
			Stack<Integer> stack = new Stack<>();
			//위에서부터 벽돌을 스택에 넣기
			for(int r=0; r<H; r++) {
				if(map[r][c]>0) stack.add(map[r][c]);
				map[r][c]=0;
			}
			//스택에 다 넣었으면 밑에서부터 쌓아주기
			for(int r=H-1; r>=0; r--) {
				if(stack.isEmpty()) break;
				map[r][c] = stack.pop();
			}
		}
		
	}
	
	static boolean checkRange(int r, int c) {
		if(0<=r && r<H && 0<=c && c<W) return true;
		else return false;
	}
}