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

 

[광고 누르면 오늘의 행운 상승!!]

 

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AW--k1o64VwDFAVg&contestProbId=AWXRQm6qfL0DFAUo&probBoxId=AXC-kM263a0DFAVX+&type=PROBLEM&problemBoxTitle=20200310&problemBoxCnt=++1+

 

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

시뮬레이션 + DFS + 중복순열+ 배열 문제 

난이도는 어렵지 않았는데 구현해야 하는 것들이 많았다.

1. map 을 복제해야 한다. 2중포문 or 1중포문 + clone() 이용
2. 해당 컬럼의 맨 처음 벽돌 가져오기  null --> continue;
3. 구슬을 떨어뜨려서 벽돌을 깬다. --> 깨진 벽돌 개수 구하기
3-1 이미 다 벽돌이 깨졌다면?? 정답 = 0, 종료
4. 화면 정리 (swap을 이용하여 아래서부터 1로 채운다.)
5. 다음 샷 발사 (재귀)

package Study0307;

import java.io.*;
import java.util.*;

public class 벽돌깨기 {
	public static final int[] dx = {1,0,-1,0};
	public static final int[] dy = {0,1,0,-1};
	public static int N,C,R,blocks,ans;
	public static boolean[][] visit;
	public static int[][] map;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 1; tc <= T; tc++) {
			ans = Integer.MAX_VALUE;
			blocks= 0;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			
			map = new int[R][C];
			visit = new boolean[R][C];
			
			int[] arr = new int[C];
			
			for (int i = 0; i < R; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < C; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(map[i][j] > 0) blocks++;
				}
			}
			
			dropMarble(N, blocks, map);
			System.out.println("#" + tc + " " + ans);
		}
	}
	private static void dropMarble(int r, int blockcnt, int[][] map) {
		if(r==0) {
			// 솔루션 사용
			ans = Math.min(ans, blockcnt);
			return;
		}
		for (int c = 0; c < C; c++) {
			// 1. map 을 복제해야 한다.
			int[][] cloned = cloneMap(map);
			// 2. 해당 컬럼의 맨 처음 벽돌 가져오기
			Brick first = getFirstBrick(c, cloned);
			// 2-1 null --> continue;
			if(first == null) continue;
			
			// 3. 구슬을 떨어뜨려서 벽돌을 깬다. --> 깨진 벽돌 개수??
			int broken = crash(first, cloned);
			// 3-1 이미 다 벽돌이 깨졌다면?? 정답 = 0, 종료
			if(broken >= blockcnt) {
				ans = 0;
				return;
			}
			// 4. 화면 정리
			cleanMap(cloned);
			// 5. 다음 샷 발사
			
			dropMarble(r-1, blockcnt-broken, cloned);
		}
		
	}
	private static void cleanMap(int[][] map) {
		for (int c = 0; c < C; c++) {
			for (int r = R-1, nr = R-1; r >=0; r--) {
				if(map[r][c] != 0) {
					int temp = map[r][c];
					map[r][c] = 0;
					map[nr--][c] = temp;
				}
			}
		}
	}
	private static int crash(Brick first, int[][] map) {
		int broken = 0;
		// 얻어 맞은 벽돌 삭제
		map[first.row][first.col] = 0;
		broken++;
		
		//주변 벽돌에 영향 주기
		for (int p = 1; p < first.pow; p++) {
			//사방 탐색
			for (int d = 0; d < 4; d++) {
				int nx = first.row + dx[d] * p;
				int ny = first.col + dy[d] * p;
				
				if(isIn(nx,ny) && map[nx][ny] != 0) {
					broken += crash(new Brick(nx,ny,map[nx][ny]) , map);
				}
			}
		}
		return broken;
	}
	private static boolean isIn(int nx, int ny) {
		return 0<=nx && 0<= ny && nx <R && ny <C;
	}
	private static Brick getFirstBrick(int c, int[][] map) {
		for (int r = 0; r < R; r++) {
			if(map[r][c] != 0) {
				return new Brick(r,c,map[r][c]);
			}
		}
		return null;
	}
	private static int[][] cloneMap(int[][] map) {
		int [][] temp = new int[R][C];
		for (int i = 0; i < R; i++) {
			temp[i] = map[i].clone();
		}
		return temp;
	}
	static class Brick{
		int row, col, pow;
		public Brick(int row ,int col, int pow) {
			this.row = row;
			this.col = col;
			this.pow = pow;
		}
		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("Brick [row=").append(row).append(", col=").append(col).append(", pow=").append(pow)
					.append("]");
			return builder.toString();
		}
		
	}
}