[중복순열, BFS] SWEA 5656번 구슬 깨기 자바 풀이 (모의 sw 역량 테스트)

sw expert academy 5656 구슬 깨기 자바(java) 풀이

• 모의 SW 역량 테스트
• sw expert academy 5656 구슬 깨기
  
  
  

문제정리

1. 구슬을 쏘아 벽돌을 깨드리려 한다. 벽돌이 있는 공간의 크기는 WxH이다.
2. 구슬은 좌우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다.
3. 벽돌은 숫자 1~9로 표현되며, 구슬이 명중한 벽돌은 상하좌우로(벽돌에 적힌 숫자-1)칸 만큼 같이 제거된다.
4. 빈 공간이 있을 경우 벽돌은 밑으로 떨어지게 된다.
5. N개의 벽돌을 떨어트려 최대한 많은 벽돌을 제거하려고 한다. 벽돌을 떨어트린 후 남은 벽돌의 개수를 구하여라.
   
   
   

문제 풀이

1. 모든 경우를 따져주기 위해서 중복 순열을 구해야 합니다. N이 3인 경우 000 ~ 999 (W=10)까지 모두 시뮬레이션 해봐야 하기 때문입니다.
2. 매번 시뮬레이션 하기 위해 원래 블록 상태를 유지해야 합니다. 그래서 배열을 복사하여 사용합니다.
3. 선택한 열에 맨 위의 블록을 찾아 큐에 넣습니다.
4. 그리고 bfs 방식으로 계속 연쇄적으로 뿌셔 나갑니다. 상하좌우로 1칸씩 늘려가며 써있는 수-1 만큼 탐색해 나갑니다.
5. 벽돌을 모두다 부셨다면 비어있는 공간을 제거하기 위해 아래에서 위로 0이 아닌 수를 탐색하여 queue에 넣습니다.
6. queue에 넣은 수를 그 열의 아래부터 쌓습니다.
7. 그리고 중복순열로 선택한 N개의 열들에 대해 반복합니다.
8. 제일 적은 수의 블록을 남기기 위해서는 제일 많이 깨트려야 합니다. 그래서 깨트린 블록 수를 최대가 되도록 update 해 나갑니다.
9. 총 블록 수에서 제일 크게 뿌신 경우의 max 값을 빼서 답을 구합니다.
   
   
   

swea 5656번 구슬 깨기 자바 코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	class Info{
	int x;
	int y;
	int n;
	Info(int x, int y, int n){
	this.x = x;
	this.y = y;
	this.n = n;
	}
	}
	class Solution {
	static int[][] bricks;
	static int N, W, H;
	static int max;
	static int[] selected;
	// 상, 하, 좌, 우
	static int[] xdir = {-1,1,0,0};
	static int[] ydir = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(br.readLine());
	for(int tc=1; tc<=T; tc++) {
	max = Integer.MIN_VALUE;
	int num=0;
	String[] temp = br.readLine().split(" ");
	N = Integer.parseInt(temp[0]);
	W = Integer.parseInt(temp[1]);
	H = Integer.parseInt(temp[2]);
	// 벽돌 정보
	bricks = new int[H][W];
	for(int i=0; i<H; i++) {
	temp = br.readLine().split(" ");
	for(int j=0; j<W; j++) {
	bricks[i][j] = Integer.parseInt(temp[j]);
	if(bricks[i][j] != 0)
	num++;
	}
	}
	selected = new int[N];
	// 모든 경우를 따져주어야 한다. 중복 순열
	perm(0);
	System.out.println("#" + tc + " " + (num - max));
	}
	}
	public static void perm(int start) {
	if(start == N) {
	Queue<Info> q = new LinkedList<>();
	int[][] copy = new int[H][W];
	int broken=0;
	// 벽돌 상태 복사
	for(int i=0; i<copy.length; i++)
	System.arraycopy(bricks[i], 0, copy[i], 0, bricks[i].length);
	for(int j=0; j<N; j++) {
	for(int i=0; i<H; i++) {
	// 선택한 열에서 맨 위 블록 찾기
	if(copy[i][selected[j]] != 0) {
	// 연쇄적으로 블록을 부시기 위해 queue에 담음
	q.offer(new Info(i,selected[j], copy[i][selected[j]]));
	copy[i][selected[j]] = 0;
	broken++;
	// 연쇄 뿌시기 시작!!
	while(!q.isEmpty()) {
	Info item = q.poll();
	int n = item.n - 1; // 벽돌에 써있는 수 -1길이 까지 탐색
	int x = item.x;
	int y = item.y;
	for(int k=1; k<=n; k++) {
	// 상, 하, 좌, 우 4방향 탐색
	for(int tt=0; tt<4; tt++) {
	int dx = x + xdir[tt]*k;
	int dy = y + ydir[tt]*k;
	// 유효한 범위이고 0과 1이 아닌 수의 경우 연쇄 반응하기 위해 queue에 담음
	// 1은 연쇄가 없기 때문에 담지 않아도 됨
	if(isValidPosition(dx, dy) && copy[dx][dy] != 0) {
	if(copy[dx][dy] != 1)
	q.offer(new Info(dx, dy, copy[dx][dy]));
	copy[dx][dy] = 0;
	broken++;
	}
	}
	}
	}
	// 정리
	// 깨진 블록들로 인해 빈 공간을 메꾼다
	if(bricks[i][selected[j]] != 0 && broken != 1) {
	for(int t=0; t<W; t++) {
	// 열 단위로 검사하기
	// 0이 아닌 수를 찾아 재정렬을 위해 queue에 담기
	Queue<Integer> temp = new LinkedList<>();
	for(int k=H-1; k>=0; k--) {
	if(copy[k][t] != 0) {
	temp.offer(copy[k][t]);
	copy[k][t] = 0;
	}
	}
	// 밑에 줄부터 쌓기
	int tt = H-1;
	while(!temp.isEmpty()) {
	copy[tt--][t] = temp.poll();
	}
	}
	}
	break;
	}
	}
	}
	max = max < broken ? broken : max;
	return;
	}
	for(int i=0; i<W; i++) {
	selected[start] = i;
	perm(start+1);
	}
	}
	public static boolean isValidPosition(int x, int y) {
	if(x < 0 || y < 0 || x >= H || y >= W) return false;
	return true;
	}
	}

view raw swea5656.java hosted with ❤ by GitHub