[SWEA-5656] 벽돌 깨기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

SW Expert Academy

이 문제는 SWEA 아카데미 모의 SW 역량테스트 문제이다.

이 문제가 SW역량평가 Advanced, 우리가 알고 있는 A레벨 정도의 문제라고 한다.

로직 자체가 어렵기 보다는, 구현을 잘 해내야 하는게 조금 어려웠다.

처음에는 한번 쏜 위치에는 공을 못 쏘는 줄 알았는데, 똑같은 곳에 또 쏠 수 있어서 그거 고치느라 시간이 조금 걸렸고, 맵을 깨진 블럭들을 없애고 남은 블럭들을 옮겨주는 과정에서 실수를 했는데 그 부분 디버깅하는데 시간이 많이 걸렸다ㅠ

 

일단 나는 입력을 받아 준 뒤,

1. 공을 쏠 위치를 중복순열을 이용해서 골라주기 (perm)

2. 골라준 위치에 공 쏘기(destroy)

  2-1. Queue 를 이용해서 상하좌우 다 깨트려주기.

  2-2. 만약 깨트리는 중에 다른 블럭 만나면, 그 블럭도 큐에 넣고 같이 돌려주기

3. 다 비었다면 temp 배열을 이용해서 블럭들을 맨 아래로 모아주기.

4. N번만큼 1-3을 반복했다면 남은 벽돌 세어주기

5. 지도 초기화 후 1번부터 반복. 

 

이 과정들을 반복해서 가장 적게 남은 벽돌의 수를 출력해준다.  

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 벽돌깨기_5656 {
	static int N,W,H;
	static int ans = 10000;
	static int[][] map, copy;
	static boolean[][] visited;
	static boolean[] check;
	static int[] selected;
	static int[] dr = {};
	static int[] dc = {};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int  T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt();
			W = sc.nextInt();
			H = sc.nextInt();
			
			map = new int[H][W];
			copy = new int[H][W];
			visited = new boolean[H][W];
			check = new boolean[W];
			selected = new int[N];
			ans = 10000;
			
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					map[i][j] = sc.nextInt();
					copy[i][j] = map[i][j];
				}
			}
			
			perm(0);
			
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void perm(int cnt) {
		if(cnt == N) {
			//공 쏠 위치 찾기
			for(int b=0; b<N; b++) {
				destroy(selected[b]);
				
				//세로로 돌면서 블럭 옮겨주기
				for(int j=0; j<W; j++) { 
					int[] temp = new int[H];
					int idx = 0;
					//세로 줄 중 0이 아닌 숫자들 temp에 넣어주기
					for(int i=H-1; i>=0; i--) {
						if(map[i][j] != 0) {
							temp[idx++] = map[i][j];
						}
					}
					
					//뒤부터 0이 아닌 숫자 넣어주기
					idx = 0;
					for(int i=0; i<H; i++) {
						map[i][j] = temp[H-1-i];
					}
				}
			}
			
			int block = 0; //이번 블럭 갯수
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					if(map[i][j] != 0)
						block++;
				}
			}
			
//			System.out.println(block);
			
//			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();
			
			
			
			//다음꺼 계산 위해 원상복구
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					map[i][j] = copy[i][j];
				}
			}

			if(ans > block) {
//				System.out.println(selected[0]+" "+selected[1]);
				ans = block;
			}

			return;
		}
		
		//공 쏠 곳 N개 뽑기
		for(int i=0; i<W; i++) {
			selected[cnt] = i;
			check[i] = true;
			perm(cnt+1);
			check[i] = false;
		}
	}
	
	//공 쏠 위치 기준으로 삭제
	static void destroy(int x) {
		Queue<Point> q = new LinkedList<>();
		
		for(int i=0; i<H; i++) {
			if(map[i][x] != 0) {
				q.add(new Point(i,x, map[i][x]));
				break;
			}
		}
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			int r = p.r;
			int c = p.c;
			
			//위
			for(int i=0; i<p.power; i++) {
				if(r-i>=0 && map[r-i][c] != 0) {
					q.add(new Point(r-i, c, map[r-i][c]));
					map[r-i][c] = 0;
				}
			}
			//아래
			for(int i=0; i<p.power; i++) {
				if(r+i<H && map[r+i][c] != 0) {
					q.add(new Point(r+i, c, map[r+i][c]));
					map[r+i][c] = 0;
				}
			}
			//왼쪽
			for(int i=0; i<p.power; i++) {
				if(c-i>=0 && map[r][c-i] != 0) {
					q.add(new Point(r, c-i, map[r][c-i]));
					map[r][c-i] = 0;
				}
			}
			//오른쪽
			for(int i=0; i<p.power; i++) {
				if(c+i<W && map[r][c+i] != 0) {
					q.add(new Point(r, c+i, map[r][c+i]));
					map[r][c+i] = 0;
				}
			}
		}
	}
	
	static class Point{
		int r,c, power;
		Point(int r, int c, int power){
			this.r = r;
			this.c = c;
			this.power = power;
		}
	}
}