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

SWEA 5656 벽돌깨기

접근방식

처음에는 DFS를 이용해서 현재 map상태에서 가장 많은 벽돌이 제거되는 벽돌을 찾고 -> 이 벽돌들을 제일 위에서 부터의 거리순으로 정렬해서 풀려고 했다.

그리디한 접근방식이라 실제로 이렇게 구현하고보니 문제가 있었다.
구슬을 쏠 수 있는 횟수 N =3(예시)
벽돌을 깼을 때 한번에 같이 없어지는 벽돌의 합을 S
해당 벽돌의 깊이(위에서 부터 벽돌까지 도달하는데 깨야하는 벽돌 수 )를 T라고 할 때
아래와 같은 경우가 발생할 수 있다.
[S =15 T= 3], [S=10 T=1], [S=8 T=1]

T가 3이기 때문에, 구슬횟수 N을 모두 사용하면 S=15블록을 제거할 수 있지만, S가 10,8인 블럭은 각각 구슬을 1번만 사용해서 각각 10, 8블록이 제거되기 때문에 더 많은 벽돌이 깨지는 경우가 존재할 수 있게된다.

여기에서 뭔가 LIS를 이용해서 최소값의 합이 최대가 되는 벽돌들을 구하면 되지 않을까 생각했는데, 문제는 벽돌들끼리의 상호작용이 있기 때문에 불가능하다고 판단했다.
무슨 말이냐면, 위에서 제시한 예시에서도 S=10, S=8이 완전 독립적으로 계산된 경우일 수도 있지만, 그렇지 않은 경우가 있을 수도 있다.
S=10인 블럭을 먼저 제거했는데, 이때 S=8에 해당하는 블럭도 제거될 수 있는 것이다. 결국에 시도해보지 않고 S와 T를 가지고만 최선의 선택이 불가능하다고 보았다.

결국 중복순열을 이용해 구슬의 횟수만큼 경우의 수를 계산해서 벽돌을 제거하고, 남은 벽돌의 수를 계산하는 방식으로 문제를 풀었다.
또 벽돌을 제거하는 방식에 DFS, BFS가 있는데, 나는 DFS를 이용해서 풀었다.
벽돌을 떨어트리는 작업에서도 while문을 이용해서 구현할 수도 있고, 나처럼 Queue를 이용해서 구현할 수도 있다.

코드

package com.algo.swea;

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


public class SWEA5656Brick {
	static class Brick {
		int x, y, size;
		public Brick(int x, int y, int size) {
			this.x = x;
			this.y = y;
			this.size = size;
		}
	}
	private static int[][] map, cmap;
	private static boolean[][] visited;
	private static int W, H, N, result;
	private static int[] pick;
	private static Stack<Brick> s;
	private static Queue<Integer> q;
	private static StringBuilder sb;
	private static int[] dx = {1,0,-1,0};
	private static int[] dy = {0,-1,0,1};

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_d9_5656.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		s = new Stack<>();
		q = new LinkedList<>();
		int TC = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		for (int testCase = 1; testCase <= TC; testCase++) {
			st = new StringTokenizer(br.readLine()," ");
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			pick = new int[N];
			map = new int[H][W];
			cmap = new int[H][W];
			visited = new boolean[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());
				}
			}//input
			result=181;
			permutation(0);
			sb.append("#").append(testCase).append(" ").append(result).append("\n");
		}//testCase 
		System.out.print(sb);
		br.close();

	}
	private static void permutation(int cnt) {
		if(cnt==N) {
			for (int i = 0; i < H; i++) {
				System.arraycopy(map[i], 0, cmap[i], 0, W);
			}
			for (int i = 0; i < N; i++) {
				remove(pick[i]);
				drop();
			}
			if(result==0) return;
			return;
		}
		for (int i = 0; i < W; i++) {
			pick[cnt]=i;			
			permutation(cnt+1);
		}
	}

	private static void drop() {
		int temp = 0;
		for (int i = 0; i < W; i++) {
			for (int j = 1; j <= H; j++) {
				int val = cmap[H-j][i];
				if(val>0) q.offer(val);
				cmap[H-j][i]=0;
			}
			int size = q.size();
			temp+=size;
			for (int j = 1; j <=size; j++) {
				cmap[H-j][i] = q.poll();
			}
		}
		result = Math.min(result, temp);

	}
	private static void remove(int col) {
		for (int i = 0; i < H; i++) {//초기
			Arrays.fill(visited[i], false);
		}
		for (int i = 0; i < H; i++) {
			if(cmap[i][col]>0) {
				s.push(new Brick(i, col, cmap[i][col]));
				break;
			}
		}
		while(!s.isEmpty()) {
			Brick temp = s.pop();
			for (int i = 0; i < temp.size; i++) { //벽돌 크기 만큼 터짐
				for (int d = 0; d < 4; d++) {
					int nx = temp.x+i*dx[d];
					int ny =  temp.y+i*dy[d];
					if(nx<0 || ny<0|| nx>=H || ny>=W) continue;
					if(visited[nx][ny] || cmap[nx][ny]==0)continue;
					visited[nx][ny]=true;
					s.push(new Brick(nx, ny, cmap[nx][ny]));
					cmap[nx][ny] =0;
				}
			}
		}
	}

}