[SWEA] 5656 - 벽돌깨기

[문제링크]

SW Expert Academy

 

0. shoot함수 : n번째 구슬을 모든 경우의 수에 대해 쏴보고, n+1번째로 재귀하는 함수

  - remove함수 : x, y좌표의 벽돌이 깨졌을 경우 모든 벽돌을 재귀로 깨는 함수

  - getDown함수 : 벽돌을 깬 후 모든 벽돌을 빈공간 없이 아래로 쌓는 함수

 

1. shoot함수가 모든 경우의 수에 대해 remove -> getDown 해본다

 

2. n번 구슬을 쐈을때 남아있는 ball값과 min을 비교, 갱신

 

* ball(remain)값을 인자로 넘기지 말고 전역변수로 관리할 수 있을것같은데, 피곤해서 포기

 

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

public class Solution{
	
	static int n,w,h,ball,min;
	static int[][]map;
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = pint(st.nextToken());
			w = pint(st.nextToken());
			h = pint(st.nextToken());
			ball = 0;
			map = 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]=pint(st.nextToken());
					if(map[i][j]!=0)ball++;
				}
			}
			min=ball;
			shoot(0,ball);
			
			sb.append("#").append(testcase).append(" ").append(min).append("\n");
		}
		System.out.println(sb);
	}
	
	static void shoot(int cnt, int remain) {
		if(cnt==n) {
			min=Math.min(min, remain);
			return;
		}
		//현재 정보 백업
		int[][]backup = new int[h][w];
		for (int x = 0; x < h; x++) {
			for (int y = 0; y < w; y++) {
				backup[x][y]=map[x][y];
			}
		}
		int ballBackup=ball;

		for (int i = 0; i < w; i++) {
			// 정보 원상복구
			for (int x = 0; x < h; x++) {
				for (int y = 0; y < w; y++) {
					map[x][y]=backup[x][y];
				}
			}
			ball=ballBackup;

			for (int j = 0; j < h; j++) {
				if(map[j][i]!=0) {
					remove(j,i); // 제거하고
					getDown(); // 아래로 정렬하고
					break;
				}
			}
			shoot(cnt+1, ball); // 다음 발사로 재귀
			
		}
	}
	
	static void remove(int x, int y) {
		int c = map[x][y];
		map[x][y]=0;
		--ball;
		for (int j = 0; j < 4; j++) {
			int tx=x, ty=y;
			for (int i = 1; i < c; i++) {
				tx += dx[j];
				ty += dy[j];
				if(tx<0 || tx>=h || ty<0 || ty>=w)break;
				if(map[tx][ty]!=0)remove(tx,ty);
			}
		}
	}
	
	static void getDown() {
		for (int i = 0; i < w; i++) {
			int cnt=h-1;
			for (int j = h-1; j >=0 ; j--) {
				if(map[j][i]!=0) {
					int t = map[j][i];
					map[j][i]=0;
					map[cnt--][i]=t;
				}
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면