(JAVA) 5656. [모의 SW 역량테스트] 벽돌 깨기

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

– 가지의 수는  (numW)^numN 이다. 여기서 numW는 최대 12이고 N은 최대 4이므로 최대 20736개의 경우를 계산해 보면 됨. DFS를 쓰면 됨.
– 선택된 column에서 가장 위의 벽돌이 어딘지 우선 탐색. (만약 벽돌이 없으면 변화가 안 생기기 때문에 바로 다음 단계로 넘어감) 그리고 그 벽돌을 removeMap에 등록 (removeMap: 제거할 벽돌 목록)
– 그 벽돌을 시작으로 해서 같이 깨지는 벽돌을 모두 탐색함. 최초 벽돌에 1차 영향을 받는 벽돌들을 removeMap에 추가하고, 크기가 1보다 큰 벽돌은 queue에 추가함.
– 이후 queue가 빌 때까지 영향 받는 벽돌 탐색 및 queue 추가 (벽돌 숫자가 1보다 큰 경우)를 수행. 단, 한 번 removeMap에 추가된 벽돌은 다시 queue 추가하지 않음.
– removeMap 작성이 완료되면 이후 필요한 벽돌들을 모두 제거한 후, 밑으로 끌어당기는 작업 수행.
– 벽돌들이 모두 밑으로 내려오면 다음 단계로 넘어감. 단 최대 단계까지 이미 수행한 경우, 남은 벽돌 수를 세서 최소값인 경우만 저장.

import java.io.*;
import java.util.*;

public class Solution {
	private static int numN = 0;
	private static int numW = 0;
	private static int numH = 0;
	
	private static int minBlocks = 0;
	
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				numN = Integer.parseInt(tmp[0]); // 구슬 쏘는 횟수
				numW = Integer.parseInt(tmp[1]); // 폭 (X)
				numH = Integer.parseInt(tmp[2]); // 높이 (Y)
				
				int[][] map = new int[numH][numW];
				
				// map 생성
				for (int i = 0; i < numH; i++) {
					tmp = reader.readLine().split(" ");
					
					for (int j = 0; j < tmp.length; j++)  // numW
						map[i][j] = Integer.parseInt(tmp[j]);
				}
				
				minBlocks = numH * numW;
				process(map);
				
				writer.write(minBlocks + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static void process(int[][] map) {
		for (int i = 0; i < numW; i++)
	        process_(1, i, map);
	}
	
	public static void process_(int numTry, int theColumn, int[][] map) {
		 // copied map
		int[][] newMap = new int[numH][numW];

	    // marked as remove map
		int[][] removeMap = new int[numH][numW];

	    // copy the map
	    for (int i = 0; i < numH; i++) {
	        for (int j = 0; j < numW; j++) {
	            newMap[i][j] = map[i][j];
	            removeMap[i][j] = 0;
	        }
	    }

	    if (newMap[numH - 1][theColumn] != 0) { // if there is any block in this column, then proceed
	        // find the topmost block in the column
	        int theRow = -1;
	        for (int i = 0; i < numH; i++) {
	            if (newMap[i][theColumn] != 0) {
	                theRow = i;
	                break;
	            }
	        }

	        // find other blocks need to be removed
	        int[] queueRow = new int[numH * numW]; //[numH * numW];
	        int[] queueColumn = new int[numH * numW];
	        int front = -1;
	        int rear = -1;

	        if (front == -1)
	            front = 0;
	        
	        rear++;
	        queueRow[rear] = theRow;
	        queueColumn[rear] = theColumn;

	        removeMap[theRow][theColumn] = 1;

	        while (front != -1 && front <= rear) { // while the queue is not empty
	            int myRow = queueRow[front];
	            int myColumn = queueColumn[front];
	            front++; // dequeue

	            int mySize = newMap[myRow][myColumn];
	            if (mySize == 1) // value is 1: it breaks alone
	                continue;

	            int upperBound = 0, lowerBound = 0, leftBound = 0, rightBound = 0;
	            
	            upperBound = myRow - (mySize - 1);
	            if (upperBound < 0)
	                upperBound = 0;

	            lowerBound = myRow + (mySize - 1);
	            if (lowerBound > numH - 1)
	                lowerBound = numH - 1;

	            leftBound = myColumn - (mySize - 1);
	            if (leftBound < 0)
	                leftBound = 0;

	            rightBound = myColumn + (mySize - 1);
	            if (rightBound > numW - 1)
	                rightBound = numW - 1;

	            for (int i = myRow - 1; i >= upperBound; i--) {
	                if (removeMap[i][myColumn] == 0) {
	                    removeMap[i][myColumn] = 1;

	                    if (newMap[i][myColumn] > 1) {
	                        rear++;
	                        queueRow[rear] = i;
	                        queueColumn[rear] = myColumn;
	                    }
	                }
	            }
	            for (int i = myRow + 1; i <= lowerBound; i++) {
	                if (removeMap[i][myColumn] == 0) {
	                    removeMap[i][myColumn] = 1;

	                    if (newMap[i][myColumn] > 1) {
	                        rear++;
	                        queueRow[rear] = i;
	                        queueColumn[rear] = myColumn;
	                    }
	                }
	            }
	            for (int i = myColumn - 1; i >= leftBound; i--) {
	                if (removeMap[myRow][i] == 0) {
	                    removeMap[myRow][i] = 1;

	                    if (newMap[myRow][i] > 1) {
	                        rear++;
	                        queueRow[rear] = myRow;
	                        queueColumn[rear] = i;
	                    }
	                }
	            }
	            for (int i = myColumn + 1; i <= rightBound; i++) {
	                if (removeMap[myRow][i] == 0) {
	                    removeMap[myRow][i] = 1;

	                    if (newMap[myRow][i] > 1) {
	                        rear++;
	                        queueRow[rear] = myRow;
	                        queueColumn[rear] = i;
	                    }
	                }
	            }
	        }

	        // remove map according to the removeMap info
	        for (int i = 0; i < numH; i++) {
	            for (int j = 0; j < numW; j++) {
	                if (removeMap[i][j] == 1)
	                    newMap[i][j] = 0;
	            }
	        }

	        // move the blocks downward
	        for (int i = 0; i < numW; i++) {
	            int downmostBlankRow = -1;
	            for (int j = numH - 1; j >= 0; j--) {
	                if (downmostBlankRow == -1 && newMap[j][i] == 0) // first mark the blank space
	                    downmostBlankRow = j;
	                else if (downmostBlankRow != -1 && newMap[j][i] > 0) { // if the block need to be moved
	                    newMap[downmostBlankRow][i] = newMap[j][i];
	                    newMap[j][i] = 0;
	                    downmostBlankRow--;
	                }
	            }
	        }
	    }
	    //else ; // no need to proceed if there is no block in this column (no change)

	    if (numTry == numN) { // calculate remaining blocks
	        int blocks = 0;
	        for (int i = 0; i < numH; i++) { 
	            for (int j = 0; j < numW; j++) {
	                if (newMap[i][j] != 0)
	                    blocks++;
	            }
	        }

	        if (blocks < minBlocks)
	            minBlocks = blocks;
	    }
	    else { // proceed
	        // if there is no remaining block, then return
	        boolean noBlocksRemaining = true;
	        for (int i = 0; i < numW; i++) {
	            if (newMap[numH - 1][i] != 0) {
	                noBlocksRemaining = false;
	                break;
	            }
	        }

	        // proceed if there is more blocks
	        if (noBlocksRemaining == false) {
	            for (int i = 0; i < numW; i++)
	                process_(numTry + 1, i, newMap);
	        }
	        else // if there is no blocks remaining, then minBlocks becomes 0
	            minBlocks = 0;
	    }
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.