[SW5656] 벽돌 깨기

 SW Expert Academy - 벽돌 깨기 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE&problemTitle=sw&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

문제 입출력

3 10 10
0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0
1 0 3 0 1 1 0 0 0 1
1 1 1 0 1 2 0 0 0 9
1 1 4 0 1 1 0 0 1 1
1 1 4 1 1 1 2 1 1 1
1 1 5 1 1 1 1 2 1 1
1 1 6 1 1 1 1 1 2 1
1 1 1 1 1 1 1 1 1 5
1 1 7 1 1 1 1 1 1 1

#1 12

 

문제 풀이

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


public class Solution {
	static int ans, T, N, W, H;
	static int[][] map, mapTemp;
	static int[] tgt;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static StringBuilder sb = new StringBuilder();


	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];
			mapTemp = new int[H][W];
			for (int i = 0; i < H; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					map[i][j] = mapTemp[i][j] = Integer.parseInt(st.nextToken());
				}

				// System.out.println(Arrays.toString(map[i]));
			}

			// 초기화
			ans = Integer.MAX_VALUE;
			tgt = new int[N];

			// 시뮬레이션
			perm(0);

			// 출력
			sb.append("#").append(t).append(" ").append(ans).append("\n");

		}

		System.out.println(sb.toString());

	} // end main


	// 중복 순열
	private static void perm(int dep) {
		if (dep == N) {
			// complete code
			// System.out.println(Arrays.toString(tgt));
			copyMap();

			for (int tx : tgt) {
				for (int y = 0; y < H; y++) {
					if (map[y][tx] != 0) {
						// 벽돌 깨기
						stroke(y, tx);

						// 칸 내리기
						down();

						break;
					}

				}

			}

			ans = Math.min(ans, check());

			return;
		}

		for (int i = 0; i < W; i++) {
			tgt[dep] = i;
			perm(dep + 1);
		}

	} // end comb


	private static void stroke(int sy, int sx) {
		Queue<int[]> q = new ArrayDeque<>();
		q.offer(new int[] { sy, sx, map[sy][sx] });
		map[sy][sx] = 0;

		while (!q.isEmpty()) {
			int[] yx = q.poll();
			int y = yx[0];
			int x = yx[1];
			int size = yx[2];

			for (int i = 1; i < size; i++) {
				for (int d = 0; d < 4; d++) {
					int ny = y + dy[d] * i;
					int nx = x + dx[d] * i;

					if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
					if (map[ny][nx] == 0) continue;

					q.offer(new int[] { ny, nx, map[ny][nx] });
					map[ny][nx] = 0;
				}

			}

		}

	} // end stroke


	// 없어진 벽돌을 내리는 함수
	private static void down() {
		Stack<Integer> stack = new Stack<>();

		for (int i = 0; i < W; i++) {
			for (int j = 0; j < H; j++) if (map[j][i] != 0) stack.add(map[j][i]);

			for (int j = H - 1; j >= 0; j--) {
				if (stack.isEmpty()) map[j][i] = 0;
				else map[j][i] = stack.pop();
			}

		}

	} // end down


	// mapTemp -> map 카피 함수
	private static void copyMap() {
		for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) map[i][j] = mapTemp[i][j];
	} // copyMap


	// 남은 벽돌의 개수를 세는 함수
	private static int check() {
		int sum = 0;
		for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) if (map[i][j] != 0) sum++;
		return sum;
	} // end check
}

• bfs 까지는 구현을 했는데.. 벽돌을 내리는 함수를 구현하지 못한 문제.
• 배열 돌리기 정말 극혐이다.

 

import java.util.Arrays;
import java.util.Stack;


public class Test {
	static int H = 4; // 높이
	static int W = 4; // 너비
	static int[][] map = {
	                { 0, 1, 0, 1 },
	                { 1, 0, 1, 0 },
	                { 0, 1, 0, 1 },
	                { 0, 0, 0, 0 },
	};


	public static void main(String[] args) {
		for (int i = 0; i < H; i++) System.out.println(Arrays.toString(map[i]));

		down();

		System.out.println();
		for (int i = 0; i < H; i++) System.out.println(Arrays.toString(map[i]));
	}


	// 없어진 벽돌을 내리는 함수
	private static void down() {
		Stack<Integer> stack = new Stack<>();

		for (int i = 0; i < W; i++) {
			for (int j = 0; j < H; j++) {
				if (map[j][i] != 0) {
					stack.add(map[j][i]);
					System.out.println("add: " + j + " " + i);
				}

			}

			for (int j = H - 1; j >= 0; j--) {
				if (stack.isEmpty()) map[j][i] = 0;
				else {
					map[j][i] = stack.pop();
					System.out.println("insert: " + j + " " + i);
				}

			}

		}

	} // end down
}

• stack 은 LIFO 가장 마지막에 넣은 것이 나온다.
• 반복문으로 열을 기준으로 모든 행을 돈다.
• 그래서 1이 나온다면 스택에 넣는다.
• 이 1을 마지막 0에 넣기 위해서 아래의 행부터 다시 올라온다.
• 만약 스택이 비어 있지 않다면 해당 열에 top 을 꺼내 넣는다.
• 만약 스택이 비어있다면 다 0으로 채워넣는다.

 

 

 

 

 

 

 

# sw 벽돌깨기 bfs # sw 벽돌 깨기 java # swea 벽돌깨기 java

---