[SWEA 5656 - Java] 벽돌 깨기

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

풀이

완전탐색과 BFS를 적절히 이용하면 되는 문제입니다.

적용되는 알고리즘 자체는 정말 간단하지만 그를 구현하는게 골치아팠습니다.

 

1. 완전탐색을 이용하기 때문에 재귀로 구현하였습니다. 다음 재귀가 호출되는 것은 다음 구슬을 벽돌에 쏘는 경우 입니다.
2. 구슬을 쏘는 경우에 대해선 완전 탐색을 하고 그 안에서 연쇄적으로 벽돌이 파괴될 수 있으므로 이는 BFS를 사용하였습니다.
3. 현재 구슬이 맞추는 벽돌의 좌표를 큐에 넣고 BFS를 시작합니다. 현재 위치와 함께 깨지는 벽돌의 숫자가 1보다 큰 경우엔 그 벽돌의 주변 벽돌도 깨는 것이 가능하므로 큐에 그 위치와 벽돌의 숫자를 넣어줍니다.
4. 이를 반복하면서 깰 수 있는 벽돌들을 모두 깨줍니다.
5. 완료후엔 중간에 빈칸이 존재할 수 있으므로 벽돌을 내려주는 연산을 합니다.
6. 그런 뒤 다음 구슬이 깨는 모든 위치에 대해 재귀를 호출하며 확인합니다.
7. 남은 벽돌의 수가 0이 되거나 N개의 구슬을 모두 쏜 경우 남는 최소 벽돌 수 와 비교해 이를 업데이트 합니다.

 

import java.util.Scanner;
import java.util.*;

public class Solution {

	static int N, W, H;
	static int answer;
	static int[][] map;
	static int[] R = {-1, 1, 0 ,0};
	static int[] C = {0, 0, 1, -1};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int tc = 1; tc<=T; tc++) {
			
			N = sc.nextInt();
			W = sc.nextInt();
			H = sc.nextInt();
			
			
			map = new int[H+1][W+1];
			int cnt = 0;

			for(int i=1; i<=H; i++) {
				for(int j=1; j<=W; j++) {
					map[i][j] = sc.nextInt();
					if(map[i][j] > 0)
						cnt++;
				}
			}
			

			answer = cnt+1;
			int[][] temp = new int[H+1][W+1];
			for(int x=1; x<=H; x++) {
				for(int y=1; y<=W; y++) {
					temp[x][y] = map[x][y];
				}
			}
			
			
			for(int i=1; i<=W; i++) {
				for(int j=1; j<=H; j++) {
					if(map[j][i] != 0) {
						crushBlock(0, j, i, cnt);
						
						for(int x=1; x<=H; x++) {
							for(int y=1; y<=W; y++) {
								map[x][y] = temp[x][y];
							}
						}
						//System.out.println(j+" "+i+" "+map[j][i]+" "+answer);
						
						break;
					}
				}
			}
			
			
			System.out.println("#"+tc+" "+answer);
		}
	}
	
	static void crushBlock (int broken, int r, int c, int rest) {
		
		Queue<Pos> q = new LinkedList<>();
		int nowR = r;
		int nowC = c;
		/*
		if(rest <= 0) {
			answer = 0;
			return;
		}*/
		if(broken == N) {
			if(rest < answer)
				answer = rest;
			return;
		}
			
		int[][] temp = new int[H+1][W+1];
		
		for(int i=1; i<=H; i++) {
			for(int j=1; j<=W; j++) {
				temp[i][j] = map[i][j];
			}
		}
		
		q.add(new Pos(nowR, nowC, map[nowR][nowC]));
		map[nowR][nowC] = 0;
		rest--;
		
		while(!q.isEmpty()) {
			Pos now = q.poll();
			
			for(int i=1; i<now.br; i++) {
				for(int j=0; j<4; j++) {
					int nextR = now.r+i*R[j];
					int nextC = now.c+i*C[j];
					
					//범위밖
					if(nextR<=0 || nextR>H || nextC<=0 || nextC>W)
						continue;
					
					//이미 사라진 벽돌 
					if(map[nextR][nextC] == 0)
						continue;
					
					// 주변을 더 깰 수 있는 경우 
					else if (map[nextR][nextC] > 1)
						q.add(new Pos(nextR, nextC, map[nextR][nextC]));
					
					map[nextR][nextC] = 0;
					rest--;
					
					
				}
			}
		}
		
		//벽돌 내리기 
		for(int j=1; j<=W; j++) {
			int down = H;
			while(down > 1) {
				if(map[down][j] == 0) {
					int next = down - 1;
                    while(next > 1 && map[next][j] == 0) 
                    	next--;
                    
                    map[down][j] = map[next][j];
                    map[next][j] = 0;

				}
				down--;
			}
		}
		
		// 벽돌 다 깼음 
		if(rest <= 0) {
			answer = 0;
			return;
		}
		
		//다음 벽돌 깨기 
		for(int x=1; x<=H; x++) {
			for(int y=1; y<=W; y++) {
				temp[x][y] = map[x][y];
			}
		}
		
		
		for(int i=1; i<=W; i++) {
			for(int j=1; j<=H; j++) {
				if(map[j][i] != 0) {
					crushBlock(broken+1, j, i, rest);
					for(int x=1; x<=H; x++) {
						for(int y=1; y<=W; y++) {
							map[x][y] = temp[x][y];
						}
					}
					break;
				}
			}
		}
		
		
		
	}
	
	static class Pos{
		int r, c, br;
		
		Pos(int r, int c, int br){
			this.r = r;
			this.c = c;
			this.br = br;
		}
	}

}