[삼성 SW Expert Academy] 5656. [모의 SW 역량테스트] 벽돌 깨기 [JAVA]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

SW Expert Academy

---

| 풀이

• step 1 : 중복순열 - dfs()

1. 선택 해야하는 개수 - ( 1 <= N <= 4 )            // 4개
2. 선택 가능한 개수 - 가짓 수 ( 0 <= W <= 12 )  // 12개
3. 따라서, O( 4^12 ) 

• step 2 : DFS - 구슬 떨어뜨려서 벽돌 깨기 ( 매개변수 : 행 , 열 , 벽돌에 적힌 숫자 ) - Bomb()

1. 연속적인 사건이 발생하기 때문에 재귀함수를 생각했다. - 줄줄이 벽돌 깨지니까 
2. 최대로 벽돌이 깨지는 경우의 수는 ( W*H 의 크기를 벗어나지 못한다. )
3. 따라서, W의 최대 12 , H의 최대 15 이므로 O(180)

How ) 4 방향 돌면서 벽돌에 적힌 숫자만큼 0으로 바꾸기 
 
 * 벽돌에 적힌 숫자가 1보다 큰게 나오면 Bomb(DFS) 돌면서 해당 위치로 부터 다시 벽돌 깨고
 * 돌아와서 남은 벽돌 제거 ( 재귀 끝난 후에 )

• O( step 1 * 2 ) => O( 4^12*180 ) 
• step 3 : 3중 for문 벽돌 깨고 남은 빈 공간 당겨주기 - pull()
• step 4 : 2중 for문 남은 벽돌의 개수 구하기 - getBlock()
• step 5 : Min 값 비교 - 라이브러리 Math.min
• step 6 : 원래 저장된 값으로 map 복사해주기 - copy()

---

| 어려웠던 점

1) if 주석처리 한 곳에서 재귀를 돌리면 StackOverflow 발생했다.

• map[nx][ny]를 바꾸지 않고 돌림 - 무한 반복돌게 된다. ( 문제 ) [ 아래처럼 해결 ] 

private static void Bomb(int x, int y, int power) {

		for (int d = 0; d < 4; d++) {

			int nx = x; // 행
			int ny = y; // 열

			int tmp = 0;
			while (tmp < power) {

				if (!(nx >= 0 && nx < H && ny >= 0 && ny < W)) {
					tmp++;
					continue;
				}

				if (map[nx][ny] > 1) {
					int t = map[nx][ny];
					map[nx][ny] = 0;
					Bomb(nx, ny, t); // 크기가 1보다 크면 연쇄 폭탄 터뜨리기
				}

				map[nx][ny] = 0;

				nx += dr[d];
				ny += dc[d];

				tmp++;
			}
		}
	}

2) 벽돌이 깨질 때 위는 깨질 필요 없다고 생각했다. 그러나 연쇄적인 반응에 의해서 위가 깨짐
 ex. 우측 -> 위방향 

3) 벽돌을 순차적으로 깨고 굳이 당길 필요가 없다고 생각했다. 

그러나 벽돌에 적힌 숫자가 밑 공간으로 채워지면서 깨지는 범위가 달라진다.

( 이런건, 문제 풀때 생각하자 ! )

---

| 코드

package 알고리즘공부하기;

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

public class 벽돌깨기_sw5656 {

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int TC, N, W, H;
	static int[][] map, temp;
	static int answer;
	static int[] sel;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		TC = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= TC; tc++) {

			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];
			sel = new int[N];
			temp = new int[H][W];
			answer = Integer.MAX_VALUE;
			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());
					temp[i][j] = map[i][j];
				}
			}

			// 1. dfs ( 가로 길이 최대 12개 ) 중복순열 구하기 - 최대 N번 ( idx == N 일때 기저조건 )
			dfs(0);

			// 2. 4개 다 선택 되었다면, 순차적으로 터뜨리기 - 이것도 재귀로
			System.out.println("#" + tc + " " + answer);

		} // end tc

	} // end main

	private static void dfs(int idx) {
		if (idx == N) {

			for (int i = 0; i < N; i++) {
				int x = GetY(sel[i]); // 터뜨릴 행
				int y = sel[i]; // 터뜨릴 열
				int power = map[x][y];
				Bomb(x, y, power);
				pull(); // 빈 공간 땡기기
			}
//			print();
			answer = Math.min(answer, getBlock());
			copy();
			return;
		}

		// 열의 개수 모두 탐색
		for (int i = 0; i < W; i++) {
			sel[idx] = i; // i 열 터뜨리기
			dfs(idx + 1);
		}

	}
	/** 빈 공간 채워주는 함수  **/
	private static void pull() {

		for (int i = 0; i < W; i++) { // 열

			for (int j = H - 1; j > 0; j--) { // 행
				if (map[j][i] == 0) {

					int target = j - 1;
					int idx = j - 1;
					// 위에 블럭 있는 위치 찾기
					while (target >= 0) {
						if (map[target][i] > 0) {
							idx = target;
							break;
						}
						target--;
					}
					map[j][i] = map[idx][i];
					map[idx][i] = 0;
				}
			}

		}
	}
	/** 테스트 함수  **/
	private static void print() {

		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("===");
	}

	/** map이 매번 바뀌니 저장해 놓은 temp로 부터 복사 해주는 함수 **/
	private static void copy() {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				map[i][j] = temp[i][j];
			}
		}
	}

	/** 벽돌의 개수 세는 함수  **/
	private static int getBlock() {
		int result = 0;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (map[i][j] > 0)
					result++;
			}
		}

		return result;
	}

	// x : 행 , y : 열
	/** 공 터뜨리는 함수 dfs로 구현 **/
	private static void Bomb(int x, int y, int power) {

		for (int d = 0; d < 4; d++) {

			int nx = x; // 행
			int ny = y; // 열

			int tmp = 0;
			while (tmp < power) {

				if (!(nx >= 0 && nx < H && ny >= 0 && ny < W)) {
					tmp++;
					continue;
				}

				if (map[nx][ny] > 1) {
					int t = map[nx][ny];
					map[nx][ny] = 0;
					Bomb(nx, ny, t); // 크기가 1보다 크면 연쇄 폭탄 터뜨리기
				}

				map[nx][ny] = 0;

				nx += dr[d];
				ny += dc[d];

				tmp++;
			}
		}
	}

	/** 공 떨어뜨릴 때 맨위에 있는 위치 찾기 **/
	private static int GetY(int c) {

		for (int r = 0; r < H; r++) {
			if (map[r][c] > 0)
				return r;
		}
		return 0;
	}

}

---

| 보완할 점

• 문제를 풀다 생각해보니, 벽돌을 깰때는 큐를 사용해서 깨는게 더 좋을 것 같다는 생각을 했다. 
• BFS 활용해서 벽돌을 깨는 방법으로 풀고 업로드 해야겠다. ↓

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

public class Solution_M5656_벽돌깨기_BFS {
	static class Point{
		int r,c,cnt;
		public Point(int r, int c, int cnt) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}
	private static int[] dr = {-1,1,0,0};
	private static int[] dc = {0,0,-1,1};
	private static int N,W,H,min;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine().trim());
		for (int t = 1; t <= T; ++t) {
				//// #1, N = 3, W = 10, H = 10
			StringTokenizer st = new StringTokenizer(in.readLine());
			N = Integer.parseInt(st.nextToken()); // 시간
			W = Integer.parseInt(st.nextToken()); // 열크기
			H = Integer.parseInt(st.nextToken()); // 행크기
			int[][] map = new int[H][W];
			for (int r = 0; r < H; ++r) {
				st = new StringTokenizer(in.readLine());
				for (int c = 0; c < W; ++c) {
					map[r][c] = Integer.parseInt(st.nextToken());
				}
			}			
			min = Integer.MAX_VALUE;
			go(0,map);
			System.out.println("#" + t + " "+min);
		}
	}

	private static boolean go(int count,int[][] map) {
		int result = getRemain(map);
		if(result == 0) {
			min = 0;
			return true;
		}
		if(count == N) {
			min = Math.min(min, result);
			return false;
		}
		int[][] newMap = new int[H][W];
		for (int c = 0; c < W; ++c) { // 매열마다 구슬 떨어드리는 시도.			
			// 구슬을 떨어뜨리면 맞는 벽돌이 있는 행 찾기
			int r=0;
			while(r<H && map[r][c]==0)r++;
			if(r==H) continue; // 모두 빈칸이면 다음 열로 시도
			
			// 터트리는 시도하기 전에 직전 count횟수까지의 맵 상태를 이용하여 배열 복사하여 초기화 
			copy(map,newMap);
			
			boom(newMap,r,c);
			down(newMap);
			if(go(count+1,newMap)) return true;
		}	
		return false;
	}
	private static void boom(int[][] map,int r,int c) {
		Queue<Point> queue = new LinkedList<Point>();
		if(map[r][c]>1) { // 주변 영향 미치는 벽돌이면 터지는 시작점으로 큐에 넣기
			queue.offer(new Point(r,c,map[r][c]));
		}
		map[r][c] = 0; // 자신은 제거 처리
		while(!queue.isEmpty()) {
			Point p = queue.poll();
			for (int d = 0; d < 4; ++d) {
				int nr = p.r,nc=p.c;
				for (int k = 1; k < p.cnt; ++k) {// 자신의 숫자-1만큼 제거처리할 벽돌 큐에 넣기
					nr += dr[d];
					nc += dc[d];
					if(nr>=0 && nr<H && nc>=0 && nc<W && map[nr][nc]!=0) {
						if(map[nr][nc]>1) {
							queue.offer(new Point(nr,nc,map[nr][nc]));
						}
						map[nr][nc] = 0;
					}
				}
			}
		}
	}
	private static void down(int[][] map) {
		for (int c = 0; c < W; ++c) {
			int r = H-1;
			while(r>0) {// 윗행은 내릴행이 없으므로 1행까지만 돌면 됨.
				if(map[r][c]==0) {// 빈칸이면 가장 가까운 빈칸이 아닌 칸 찾기
					int nr = r-1; // 직전행부터
					while(nr>0 && map[nr][c]==0) --nr; // 빈칸이면 계속 윗행으로
					map[r][c] = map[nr][c];// 현재행에 남은 벽돌이나 결국 맨윗행의 0이 채워짐.
					map[nr][c] = 0; // 찾은 윗행은 벽돌이 떨어졌으므로 빈칸 처리
				}
				--r;
			}
		}
	}
	private static int getRemain(int[][] map) {
		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;
	}
	private static void copy(int[][] map,int[][] newMap) {
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				newMap[r][c] = map[r][c];
			}
		}
	}
}

---