[SWEA 5656] 벽돌 깨기 (Java)

SWEA 5656 벽돌 깨기

시뮬레이션 문제로 구현해야하는 것이 많아서 까다로웠다. 하지만 특별히 신경써야하는 부분 없이 문제에 주어진 사항만 구현하면 통과할 수 있는 문제였다. 내 구현력이 얼마나 부족한지도 느낄 수 있었다.

문제 풀이

어떻게 풀이를 할지에 대한 생각은 문제를 보고 바로 떠올랐다.
1. 구슬을 N번 떨어뜨릴 때 선택할 수 있는 열에 대한 모든 경우의 수를 구한다.
2. 모든 경우의 수를 따라서 구슬을 떨어뜨려 본다.
3. N번 떨어뜨린 후(한 가지 경우) 남아있는 벽돌의 갯수를 세어본다.
4. 경우를 수행할 때 마다 결과값을 최솟값으로 갱신한다.

하지만, 구현으로 넘어가자 생각해야 할 것이 많았다.

• 사방탐색이지만 퍼져나가는 형태가 아닌 한 지점을 기준으로 계속 나아가기
  - 기본적인 BFS를 약간 변형하여 계속 나아가게 하였다. now.w + dir[d][1] * r; 와 같이 작성하면 기준을 변경하지 않고 한 방향으로 계속 나아갈 수 있다.
• 배열에서 원소들이 듬성듬성 (마치 희소배열)있을 때 한 쪽 방향으로 원소들을 몰아 넣기
  - 아래에서 부터 탐색하여 원소가 존재하는(0이 아닌) 경우 Queue에 삽입, 하나씩 꺼내어 다시 아래에서 부터 채우고 Queue가 비었을 경우에는 0으로 채운다.
• 부셔야할 벽돌을 찾는 것과 부시는 것을 동시에 해도 되는가?
  - 처음에는 따로 해야된다고 생각했다.(간섭에 의해서 문제가 생길 것이라고 생각함)
  • visited를 사용하여 간섭을 피하고 찾는 것과 부시는 것을 동시에 수행하였다.

구현 코드

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

public class S5656_모의벽돌깨기 {
	// Queue에 넣을 객체 좌표 값과 벽돌이 깨질 때 범위를 필드로 가지고 있다.
	static class Brick {
		int h, w, range;
		
		public Brick(int h, int w, int range) {
			this.h = h;
			this.w = w;
			this.range = range;
		}
	}
	
	static Queue<Brick> q;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우 

	static int[] spots;
	static int[][] map;
	static boolean[][] visited;
	static int ans;
	static int T, N, W, H;

	static BufferedReader br;
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));

		T = stoi(br.readLine());

		for (int t = 1; t <= T; ++t) {
			st = new StringTokenizer(br.readLine());
			N = stoi(st.nextToken());
			W = stoi(st.nextToken());
			H = stoi(st.nextToken());
			
			q = new LinkedList<>();
			spots = new int[N];
			map = new int[H][W];
			ans = Integer.MAX_VALUE;

			for (int h = 0; h < H; ++h) {
				st = new StringTokenizer(br.readLine());
				for (int w = 0; w < W; ++w) {
					map[h][w] = stoi(st.nextToken());
				}
			}

			makeSet(0);

			System.out.println("#" + t + " " + ans);

		}
	}

	// spots를 지정해주는 함수
	private static void makeSet(int spot) {
		if (spot == N) {
			// 벽돌 선별 및 부시기
			int[][] copy = copyMap();
			int brick = 0;

			for (int i = 0; i < N; ++i) {
				visited = new boolean[H][W];
				selectAndCresh(copy, spots[i]);
				compact(copy);
			}
			
			brick = count(copy);
			// 현재 남은 벽돌 수와 지금까지 가장 적게 남은 벽돌수를 비교해 ans 갱신
			ans = ans > brick ? brick : ans;

			return;
		}

		for (int w = 0; w < W; ++w) {
			spots[spot] = w;
			makeSet(spot + 1);
		}
	}

	// 남은 벽돌 개수를 세어보는 함수
	private static int count(int[][] copy) {
		int brick = 0;
		
		for (int h = 0; h < H; ++h) {
			for (int w = 0; w < W; ++w) {
				if(copy[h][w] > 0) brick++;
			}
		}
		return brick;
	}
    
	// 벽돌이 부셔진 이후에 벽돌을 바닥으로 몰아넣는 함수
	private static void compact(int[][] copy) {
		Queue<Integer> temp;
		
		for(int w = 0 ; w < W ; ++w) {
			temp = new LinkedList<>();
			
			for(int h = H - 1 ; h >= 0 ; --h) {
				if(copy[h][w] > 0) temp.offer(copy[h][w]);
			}
			
			for(int h = H - 1 ; h >= 0 ; --h) {
				if(!temp.isEmpty()) {
					copy[h][w] = temp.poll();
				} else {
					copy[h][w] = 0;
				}
			}
		}
	}

	// 구슬과 부딪혔거나 연쇄반응을 일으킨 벽돌을 찾아 부시는 함수
	private static void selectAndCresh(int[][] copy, int spot) {
		// spot에서 떨어진 구슬이 가장 처음 만나는 벽돌을 찾는 부분
		for(int h = 0 ; h < H ; ++h) {
			if(copy[h][spot] > 0) {
				q.offer(new Brick(h, spot, copy[h][spot]));
				break;
			}
		}
		
		while(!q.isEmpty()) {
			Brick now = q.poll();
			int nh, nw;
			
			for(int d = 0 ; d < 4 ; ++d) {
				for(int r = 0 ; r < now.range ; ++r) {
					nh = now.h + dir[d][0] * r;
					nw = now.w + dir[d][1] * r;

					if(nh >= 0 && nh < H && nw >= 0 && nw < W && !visited[nh][nw]) {
						visited[nh][nw] = true;
						q.offer(new Brick(nh, nw, copy[nh][nw]));
						copy[nh][nw] = 0;
					}
				}
			}
		}
	}

	private static int[][] copyMap() {
		int[][] arr = new int[H][W];

		for (int h = 0; h < H; ++h) {
			for (int w = 0; w < W; ++w) {
				arr[h][w] = map[h][w];
			}
		}

		return arr;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}

}