문제

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

코드 (Java)

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

class Solution
{
	private static int N, W, H;
	private static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
	
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T=Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			int min = 0;
			
			int[][] board = new int[H][W];
			for (int row = 0; row < H; ++row) {
				st = new StringTokenizer(br.readLine().trim());
				for (int col = 0; col < W; ++col) {
					board[row][col] = Integer.parseInt(st.nextToken());
					if (board[row][col] != 0) min++;
				}
			}
			
			//recursively find the answer
			for (int col = 0; col < W; ++col) {
				min = Math.min(min, solve(board, N, col));
			}
			
			bw.write("#" + test_case + " " + min + "\n");
		}
		
		bw.flush();
		bw.close();
	}
	
	public static int solve(int[][] board, int remainingMarble, int dropW) {
		int min = 0;
		int destroyed = 0;
		
		//setup for result board
		int[][] resultBoard = new int[H][W];
//		System.out.printf("remaining %d, dropW %d\n", remainingMarble, dropW);
		for (int row = 0; row < H; ++row) {
			for (int col = 0; col < W; ++col) {
				resultBoard[row][col] = board[row][col];
				if (resultBoard[row][col] != 0) min++;
//				System.out.printf("%d ", resultBoard[row][col]);
			}
//			System.out.print("\n");
		}
//		System.out.print("\n");
		//drop at position dropW
		//1. find the top block
		int dropH = -1;
		for (int row = 0; row < H; ++row) {
			if (resultBoard[row][dropW] != 0) {
				dropH = row;
				break;
			}
		}
		
//		System.out.println(dropH);
		
		//2-1. case of no block existing in column dropW. continue next step or terminate
		if (dropH == -1) {
			if (remainingMarble >= 1) {
				return min;
			} else {
				for (int col = 0; col < W; ++col) {
					min = Math.min(min,  solve(resultBoard, remainingMarble - 1, col));
				}
				return min;
			}
		}
		
		//2-2. There is a block to destroy. We do BFS.
		Queue<int[]> q =  new LinkedList<int[]>();
		boolean[][] visited = new boolean[H][W];
		visited[dropH][dropW] = true;
		destroyed++;
		
		for (int i = 1; i <= resultBoard[dropH][dropW] - 1; ++i) {
			for (int idx = 0; idx < 4; ++idx) {
				int newH = dropH + dir[idx][0] * i;
				int newW = dropW + dir[idx][1] * i;
				if (newH < 0 || newH >= H || newW < 0 || newW >= W) continue;
				visited[newH][newW] = true;
				if (resultBoard[newH][newW] == 0) continue;
				q.add(new int[] {newH, newW});
				destroyed++;
			}
		}
		
		resultBoard[dropH][dropW] = 0;
		
		while (!q.isEmpty()) {
//			System.out.println("itered");
			int[] curPos = q.poll();
			int curH = curPos[0];
			int curW = curPos[1];
			
			for (int i = 1; i <= resultBoard[curH][curW] - 1; ++i) {
				for (int idx = 0; idx < 4; ++idx) {
					int newH = curH + dir[idx][0] * i;
					int newW = curW + dir[idx][1] * i;
					if (newH < 0 || newH >= H || newW < 0 || newW >= W || visited[newH][newW]) continue;
					visited[newH][newW] = true;
					if (resultBoard[newH][newW] == 0) continue;
					q.add(new int[] {newH, newW});
					destroyed++;
				}
			}
			
			resultBoard[curH][curW] = 0;
		}
		
		min -= destroyed;

		if (remainingMarble <= 1) {
			//it was the last marble
			return min;
		} else {
			//3. we reorganize the board and recrusively solve.
			for (int col = 0; col < W; ++col) {
				int mostBotZero = -1;
				for (int row = H-1; row >= 0; --row) {
					if (resultBoard[row][col] == 0) {
						if (mostBotZero == -1) mostBotZero = row;
					}
					else if (mostBotZero != -1) {
						resultBoard[mostBotZero][col] = resultBoard[row][col];
						resultBoard[row][col] = 0;
						mostBotZero = mostBotZero - 1;
					}
				}
			}
			for (int col = 0; col < W; ++col) {
				min = Math.min(min,  solve(resultBoard, remainingMarble - 1, col));
			}
			return min;
		}
	}
}

풀이

• BFS + 시뮬레이션 + 구현 + 재귀 + 브루트포스

• 아이디어 자체는 간단한데 단계 구별 후 각 단계별로 구현을 하는 것이 좀 복잡하다.

  • 범위가 작아서 브루트포스가 가능하다. 다만 이전 결과들을 활용하기 위해 재귀를 사용하기로 결정.
  • 깨는 위치를 잘 찾고, 깨는 행위는 BFS를 시뮬레이션.
  • 이후 블럭들의 최종 위치도 잘 계산해야 한다.