[Java Algorithm] 벽돌 깨기 SWEA #5656

문제

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

SW Expert Academy

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Solution {
	
	static int n, w, h;
	static int[][] map, memory;
	static boolean[][] visited;
	static int[] nums;
	static int ans;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder out = new StringBuilder();
		
		int tc = Integer.parseInt(in.readLine());
		for(int t = 1; t <= tc; t++) {
			st = new StringTokenizer(in.readLine());
			n = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			map = new int[h][w];
			memory = new int[h][w];
			for(int i = 0; i < h; i++) {
				st = new StringTokenizer(in.readLine());
				for(int j = 0; j < w; j++) {
					int now = Integer.parseInt(st.nextToken());
					map[i][j] = now;
					memory[i][j] = now;
				}
			}
			
			ans = Integer.MAX_VALUE;
			makeSet();
			makePermu(0, new int[n]);
			
			out.append("#" + t + " " + ans + "\n");
		}
		System.out.print(out);
	}
	
	public static void makeSet() { // 0부터 w-1까지, 구슬이 떨어질 수 있는 위치들을 담는 집합 만들기
		nums = new int[w];
		for(int i = 0; i < w; i++) nums[i] = i;
	}
	
	public static void makePermu(int nth, int[] choosed) { // 중복 순열 (구슬이 떨어질 수 있는 위치들의 모든 순열)
		if(nth == choosed.length) {
			oneCase(choosed);
			return;
		}
		
		for(int i = 0; i < nums.length; i++) {
			choosed[nth] = nums[i];
			makePermu(nth+1, choosed);
		}
	}
	
	public static void oneCase(int[] choosed) { // 하나의 순열에 대한 시뮬레이션
		for(int i = 0; i < n; i++) {
			int y = choosed[i];
			for(int x = 0; x < h; x++) {
				if(map[x][y] > 0) { // 첫 번째 벽돌을 만났을 때
					Deque<int[]> que = new ArrayDeque<>();
					que.add(new int[]{x, y, map[x][y]});
					destroy(que);
					fall();
					break;
				}
			}
		}
		findAns();
		initMap();
	}
	
	public static void destroy(Deque<int[]> que) { // 하나의 구슬에 의한 벽돌들의 부서짐을 표현
		visited = new boolean[h][w];
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int x = now[0];
			int y = now[1];
			int num = now[2];
			for(int i = 0; i < h; i++) { // 상, 하
				if(i < x-num+1 || i > x+num-1 || visited[i][y] == true) continue;
				que.add(new int[]{i, y, map[i][y]});
				map[i][y] = 0;
				visited[i][y] = true;
			}
			for(int i = 0; i < w; i++) { // 좌, 우
				if(i < y-num+1 || i > y+num-1 || visited[x][i] == true) continue;
				que.add(new int[]{x, i, map[x][i]});
				map[x][i] = 0;
				visited[x][i] = true;
			}
		}
	}
	
	public static void fall() { // 하나의 구슬에 대한 벽돌 부숨이 끝나면, 벽들들을 아래로 떨어뜨리기
		for(int y = 0; y < w; y++) {
			for(int x = h-1; x > 0; x--) { // 맨 윗 칸은 빈 칸이어도 떨어뜨릴 벽돌이 없으므로, 맨 윗칸의 바로 아랫칸까지만 탐색
				if(map[x][y] == 0) {
					for(int a = x-1; a >= 0; a--) {
						if(map[a][y] > 0) {
							map[x][y] = map[a][y];
							map[a][y] = 0;
							break;
						}
					}
				}
			}
		}
	}
	
	public static void findAns() { // 남은 벽돌 수를 세고, 최솟값 갱신
		int cnt = 0;
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				if(map[i][j] > 0) cnt++;
			}
		}
		
		ans = Math.min(ans, cnt);
	}
	
	public static void initMap() { // 하나의 조합에 대한 연산을 끝내면 map 배열 다시 원상복귀
		for(int i = 0; i < h; i++) {
			System.arraycopy(memory[i], 0, map[i], 0, memory[i].length);
		}
	}
}

👉 시뮬레이션, 구현 + 순열, BFS 문제

 

makePermu 메서드를 통해 중복 순열을 만들어서 구슬이 떨어질 수 있는 모든 경우의 수를 구했고,

하나의 순열을 완성할 때마다 oneCase 메서드를 호출하여 해당 순열의 연산 결과를 구했다.

 

oneCase 메서드에서는 순열에 주어진 열을 위에서부터 탐색하며 

구슬을 던졌을 때 만날 수 있는 첫 번째 벽돌을 찾아주었고,

찾았을 시에는 destroy 메서드를 호출하여 BFS 탐색을 통해 부술 수 있는 벽돌을 찾아 부쉈다.

 

destroy 메서드가 종료되었을 때는 fall 메서드를 호출하여 map의 빈 칸들을 채워주었다.

map의 아래에서부터 탐색하며 빈 칸 발견 시, 위로 탐색하여 찾은 벽돌을 하나씩 옮겨주는 방식으로 구현했다.

 

하나의 수열에 대한 모든 연산을 마쳤을 때는 벽돌의 개수를 세어준 뒤 최솟값을 갱신하고,

map 배열을 다시 원상복구 해주어 다음 순열에 대한 연산을 진행할 수 있도록 만들었다.

 

💡 피드백

• 처음에 잘못 생각해서 중복 순열이 아닌 중복 조합을 구했다가,, 빙빙 돌아서 문제를 해결했다.ㅜㅜ
  구슬들을 같은 위치에 던지더라도 순서가 바뀌면 결과가 달라질 수 있기 때문에 순열로!! 해야한다.
• 효율에 대한 부분은 별로 생각하지 못하고 풀이했는데, 벽돌들을 부순 뒤 빈 칸을 채우는 과정에서
  더 효율적인 방법이 있을 것 같다. 다시 한 번 생각해봐야겠다.