[SWEA] 모의 SW 역량 테스트 5656번 벽돌 깨기 (JAVA)

문제 출처 - SW Expert Academy

문제는 여기

SW Expert Academy

[문제] 

구슬을 쏘아 벽돌을 깨트리는 게임을 하려고 한다.

구슬은 N번만 쏠 수 있고, 벽돌들의 정보는 아래와 같이 W x H 배열로 주어진다.

( 0 은 빈 공간을 의미하며, 그 외의 숫자는 벽돌을 의미한다. )

게임의 규칙은 다음과 같다.

① 구슬은 좌, 우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다.

② 벽돌은 숫자 1 ~ 9 로 표현되며,

   구슬이 명중한 벽돌은 상하좌우로 ( 벽돌에 적힌 숫자 - 1 ) 칸 만큼 같이 제거된다.

아래는 벽돌에 적힌 숫자와, 구슬이 명중했을 시 제거되는 범위의 예이다.

③ 제거되는 범위 내에 있는 벽돌은 동시에 제거된다.

예를 들어 아래와 같이 4 번 벽돌에 구슬이 명중할 경우,

9번 벽돌은 4 번 벽돌에 반응하여,

동시에 제거된다.

④ 빈 공간이 있을 경우 벽돌은 밑으로 떨어지게 된다.

N 개의 벽돌을 떨어트려 최대한 많은 벽돌을 제거하려고 한다.

N, W, H, 그리고 벽돌들의 정보가 주어질 때,

▶ 남은 벽돌의 개수를 구하라!

[입력]

가장 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,

그 다음 줄부터 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 N, W, H 가 순서대로 공백을 사이에 두고 주어지고,

다음 H 줄에 걸쳐 벽돌들의 정보가 1 줄에 W 개씩 주어진다.

[출력]

출력은 #t 를 찍고 한 칸 띄운 다음 정답을 출력한다.

(t 는 테스트 케이스의 번호를 의미하며 1 부터 시작한다)

 

 

---

[풀이]

1. 똑같은 자리에 계속해서 구슬을 던질 수 있기 때문에 중복이 가능하고, 순서가 중요하기 때문에 순열이다. (중복 순열)

2. 중복 순열로 구슬의 위치를 구하고 나면 해당 값으로 BFS 탐색을 한다.

3. BFS 탐색을 하면서 map[x][y]에 적힌 값만큼 연쇄적으로 폭발하기 때문에 그 값만큼 반복을 시킨다

4. BFS 탐색을 하고 나면 삭제된 블럭을 제외하고 블록을 아래로 모아준다.

5. 2~4번을 반복해 최소값을 구해 출력한다.

[접근]

1. 어떤 위치에 구슬을 던져야 할지를 중복 순열로 선택해준다.

2. BFS 탐색을 하면서 map[x][y]값만큼 범위를 줘야 한다.

3. 블록을 아래로 내릴 때 값을 어떻게 처리해야 하는가?를 생각했는데 위에서부터 스택에 값을 담아주고 밑에서부터 스택의 값을 빼주면서 넣어준다.

[코드]

package swet;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution_test_5656 {
	static int T; // 테케수
	static int N; // 구슬의 수
	static int W; // 열
	static int H; // 행
	static int map[][]; // map
	static int copy[][]; // map을 초기화할때 사용할 copy배열
	static int numbers[]; // 중복 순열에서 선택한 값을 저장하기 위한 배열
	static int min;
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer 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];
			copy = new int[H][W];
			numbers = new int[N];
			min = Integer.MAX_VALUE;
			
			// map 입력 받기
			for (int i = 0; i < H; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					map[i][j] = copy[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			// 중복 순열 돌리기
			perm(0);
			System.out.println("#" + t + " " + min);
		}
	}

	public static void perm(int cnt) {
		if (cnt == N) {
			// 탐색 시작
			start(numbers);
			// 최소값을 갱신
			min = Math.min(min, countMap());
			// map을 초기화
			mapcopy();
			
			return;
		}
		
		// 중복을 포함한 순열을 구한다.
		for (int i = 0; i < W; i++) {
			numbers[cnt] = i;
			perm(cnt + 1);
		}
	}
	
	public static void start(int[] arr) {
		int x = 0;
		int y = 0;
		
		for (int i = 0; i < N; i++) { // 구슬의 개수만큼 반복
			for (int j = 0; j < H; j++) { // 열은 고정이므로 행만 이동
				if (map[j][arr[i]] != 0) { // 내려가면서 0이 아니면 맨 위의 블록이라는 소리
					x = j; // 해당 행
					y = arr[i]; // 해당 열
					break;
				}
			}
			bfs(x, y); // bfs 탐색 시작
			blockdown(); // 벽돌이 부서지고 위에 있던 블록이 아래로 내려옴
		}
	}
	
	public static void blockdown() {
		Stack<Integer> s = new Stack<>();
		
		for (int i = 0; i < W; i++) { // 열만큼 반복
			for (int j = 0; j < H; j++) { // 행만큼 반복
				if (map[j][i] != 0) // 0이 아니면 벽돌이니까
					s.add(map[j][i]); // 벽돌의 값을 저장
			}
			for (int j = H - 1; j >= 0; j--) { // 밑에서부터 올라가면서
				if (s.isEmpty()) // 스택이 비었다면 0으로
					map[j][i] = 0;
				else // 스택이 남아있다면
					map[j][i] = s.pop(); // 스택의 값을 map에 저장
			}
		}
	}
	
	public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {x, y, map[x][y]});
		map[x][y] = 0;
		
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int power = cur[2];
			
			for (int i = 1; i < power; i++) { // 블록의 숫자만큼 반복
				for (int j = 0; j < 4; j++) {
					int nx = cur[0] + dr[j] * i; // 블록의 숫자만큼 움직여야하니까
					int ny = cur[1] + dc[j] * i;
					
					// 범위를 벗어나거나 블록이 아닌 경우
					if (nx < 0 || nx >= H || ny < 0 || ny >= W || map[nx][ny] == 0)
						continue;
					
					if (map[nx][ny] != 0) { // 0이 아니라면 블록이니까
						q.add(new int[] {nx, ny, map[nx][ny]}); // 해당 블록을 큐에 넣어주고
						map[nx][ny] = 0; // 폭발 처리고 0으로 바꿔준다.
					}
				}
			}
		}
	}
	
	// map에 몇개의 블록이 남았는지 수를 세기 위한 함수
	public static int countMap() {
		int count = 0;
		
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (map[i][j] != 0)
					count++;
			}
		}
		return count;
	}
	
	// map을 초기화하는 함수
	public static void mapcopy() {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				map[i][j] = copy[i][j];
			}
		}
	}
}