[SWEA] 5656 벽돌깨기

1. 문제

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

SW Expert Academy

2. 접근방법

꽤나 재밌는 구현문제 였다.

 

우선 어느 위치에 떨궈야 가장 많은 벽돌을 부술 수 있는지를 구하기 위해

 

모든 위치에 다 떨어뜨려봐야한다.

그것을 위해 백트레킹을 이용한다.

 

기존 맵과 지금껏 부순 벽돌갯수를 temp에 저장해두고

모든 W에 대해서 부숴보고 되돌리고 부수고 되돌리고를 반복한다.

 

부술때 연쇄되서 폭발하는 것은 pung함수를 재귀로 구현해서 만들었다.

 

그리고 폭발이 끝난뒤 떠있는 벽돌을 떨어뜨리는 작업은 그냥 러프하게

모든 W에서 0을 찾으면 그 위를 쭉 보면서 다른숫자가 있으면 0위치로 옮겨오게 하였다.

3. 자바 코드

package D4;

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

public class P5656벽돌깨기 {
	
	static int map[][],N,W,H,result,max,rock;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1 ; tc<=T ; tc++) {
			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];
			result = 0;
			max = 0;
			rock = 0;
			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());
					if(map[i][j] != 0)
						rock++;
				}
			}
		
			go(0);
			System.out.println("#"+tc+" "+ (rock - max));
		}
	}
	static void go(int cnt) {
		if(cnt == N) {
			max = Math.max(max, result);
			return;
		}
		int tempmap[][] = new int[H][W];
		for(int j = 0 ; j < H ; j++)
			tempmap[j]  = map[j].clone();
		int tempresult = result;
		for(int i = 0 ; i < W ; i++) {
			dropRock(i);
			go(cnt+1);
			result = tempresult;
			for(int j = 0 ; j < H ; j++)
				map[j]  = tempmap[j].clone();
		}
		
		
		
	}
	static int dr[] = {1,-1,0,0};
	static int dc[] = {0,0,1,-1};
	
	static void dropRock(int w) {
		for(int i = 0 ; i < H ; i++) {
			if(map[i][w] != 0) {
				pung(i,w);
				drop();
				break;
			}
		}
	}
	static void pung(int x, int y) {
		int size = map[x][y];
		map[x][y] = 0;
		result++;
		for(int d = 0 ; d < 4 ; d++) {
			int row = x;
			int col = y;
			for(int s = 1 ; s< size; s++) {
				row = row+dr[d];
				col = col+dc[d];
				
				if( row < 0 || col < 0 || row>= H ||col>=W)
					break;
				if(map[row][col] == 0)
					continue;
				if(map[row][col] > 1) {
					pung(row,col);
					continue;
				}
				result++;
				map[row][col] = 0;
			}
		}
	}
	static void drop() {
		for(int i = 0 ; i < W ; i++) {
			for(int j = H-1 ; j >=0 ; j--) {
				if(map[j][i] == 0) {
					for(int k = j-1 ; k >= 0 ; k--) {
						if(map[k][i] != 0) {
							map[j][i] = map[k][i];
							map[k][i] = 0; 
							break;
						}
					}
				}
			}
		}
	}
	
	

}

4. 마치며

이 정도 난이도의 구현문제들이 딱 머리 안아프게 재밌는거 같다~