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

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

SW Expert Academy

이러한 문제는 삼성 역량테스트에 주로 나오는 시뮬레이션 유형이다.

 

문제 풀이

1. W, 열의 개수 중에 N개를 중복 조합으로 선택한다.
2. 그 위치에 구슬을 떨어트린후 BFS로 이어나가면서 터트린다.
3. 벽돌을 바닥까지 내려준다.
4. 남아있는 개수가 가장 작은 수를 출력한다.

 

이 문제는 이렇게 적으면 간단하지만 중간에 실수를 하게 되면 꼬이게 되는 그런 시뮬레이션 문제이다.

 

n개의 위치를 중복 순열로 하면서 정해주는 과정이다.

 

2단계인 BFS로 터트려주는 과정이다. 위,오른쪽,아래,왼쪽 순서로 탐색을 하며 방문했다면 넘어가고 아니라면 넣어준다.

 

3단계인 아래로 당겨주는 과정이다.

 

이 과정을 거쳐 작은개수를 리턴하는 것이다.

 

이러한 시뮬레이션 문제는 함수로 각각을 나눠 순서대로 계산을 하면서 생각하는 것이 중간의 오류를 찾아내기 좋다.

 

전체 코드

import java.awt.Point;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static Queue<Point> q;// 1이상인 벽돌 넣는 함수
	static int div[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int result, num, N, W, H;// 결과, 수세기,구슬수,가로,세로

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int t = kb.nextInt();
		for (int i = 1; i <= t; i++) {
			q = new LinkedList<Point>();
			result = 100000;
			N = kb.nextInt();
			W = kb.nextInt();
			H = kb.nextInt();
			int map[][] = new int[H][W];
			for (int k = 0; k < H; k++) {
				for (int j = 0; j < W; j++) {
					map[k][j] = kb.nextInt();
				}
			}
			for (int j = 0; j < W; j++) {
				start(0, map, j);
			}
			if (result == 100000) {
				System.out.println("#" + i + " " + 0);
			} else
				System.out.println("#" + i + " " + result);
		}
	}

	public static void start(int k, int map1[][], int w) {
		int map[][] = new int[H][W];
		for (int i = 0; i < H; i++) {
			map[i] = Arrays.copyOf(map1[i], W);
		} // 맵복사
		if (k == N) {
			solves(map);
			return;
		} // 구슬 개수 끝
		int h = 0;
		while (map[h][w] == 0) {// 0이 아닌지점찾기
			h++;
			if (h >= H)
				return; // 세로줄 전체가 0인경우
		}
		q.add(new Point(h, w));
		fight(map);
		down(map);
		for (int j = 0; j < W; j++) {
			start(k + 1, map, j);
		}
	}

	private static void down(int[][] map) {
		// TODO Auto-generated method stub
		for (int i = 0; i < W; i++) {
			k: for (int j = H - 1; j > 0; j--) {
				if (map[j][i] == 0) {
					int g = j - 1;
					while (map[g][i] == 0) {
						g--;
						if (g < 0)
							break k;
					}
					map[j][i] = map[g][i];
					map[g][i] = 0;
				}
			}
		}
	}


	private static void fight(int[][] map) {
		// TODO Auto-generated method stub
		boolean visit[][] = new boolean[H][W];
		visit[q.peek().x][q.peek().y] = true;
		while (!q.isEmpty()) {
			Point next = q.remove();
			int num = map[next.x][next.y];
			map[next.x][next.y] = 0;
			for (int i = 0; i < 4; i++) {
				for (int j = 1; j < num; j++) {
					int x1 = next.x + j * div[i][0];
					int y1 = next.y + j * div[i][1];
					if (x1 < 0 || x1 >= H || y1 < 0 || y1 >= W) {
						break;
					}
					if (visit[x1][y1]) {
						continue;
					}
					q.add(new Point(x1, y1));
				}
			}
		}
	}

	public static void solves(int map[][]) {
		num = 0;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (map[i][j] != 0) {
					num++;
				}
				if (num > result)
					return;
			}
		}
		if (num < result)
			result = num;
		return;
	}

}