[백준] 17136. 색종이 붙이기 (Java)

 

문제

17136번: 색종이 붙이기

 

알고리즘

브루트포스, 백트래킹

 

풀이

그리디 문제로 보일 수 있으나 모든 경우의 수를 탐색해야하는 완전 탐색 + 백트래킹 문제이다.

(0, 0) 부터 (9, 9) 까지 각 좌표마다 각 색종이를 붙일 수 있다면 붙이고, 모든 1에 색종이를 붙였을 때 색종이 개수를 최솟값과 비교해 갱신하면 된다.

 

1. 좌표: (0, 0) 부터 (9, 9) 까지

2. 색종이 크기: 5 부터 1 까지

3. 해당 크기의 색종이가 남아있다면 

4. 해당 좌표에 해당 크기의 색종이를 붙일 수 있는지 검사

- 해당 좌표부터 색종이 크기만큼의 칸이 모두 1이라면 true

 

5. 붙일 수 있다면 붙이기

- 해당 좌표부터 색종이 크기만큼의 칸을 모두 2로 변경하여 다른 칸과 구분

 

 

* 재귀 호출 반환 후 색종이를 떼는 작업 ( board 복원)을 해주어야한다.

 

* 5개의 색종이를 다 붙여본 후 (반복문을 빠져나간 뒤)  반환해주어야한다.

반환하지 않으면 다음 좌표에 색종이를 붙이러가게 된다.

그렇게 되면 다음 좌표에 색종이를 붙이고 다시 이전 좌표에 색종이를 붙이는 식으로 불필요한 과정을 무한 루프라고 생각할만큼 매우 많이 반복해 시간 초과가 난다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int board[][], min, remain[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		board = new int[10][10];
		remain = new int[] { 0, 5, 5, 5, 5, 5 };

		int left = 0;
		for (int i = 0; i < 10; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 10; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());

				if (board[i][j] == 1) {
					left += board[i][j];
				}
			}
		}

		min = Integer.MAX_VALUE;
		dfs(0, 0, left);

		if (min == Integer.MAX_VALUE)
			min = -1;
		System.out.println(min);
	}

	static void dfs(int pos, int count, int left) {

		if (count >= min)
			return;

		if (left == 0) {
			min = Math.min(min, count);

			return;
		}

		int y = pos / 10;
		int x = pos % 10;
		for (int i = y; i < 10; i++) {
			for (int j = (y == i ? x : 0); j < 10; j++) {

				if (board[i][j] != 1)
					continue;

				for (int k = 5; k >= 1; k--) {

					// 복사
					int[][] copyBoard = new int[10][10];
					for (int q = 0; q < 10; q++)
						System.arraycopy(board[q], 0, copyBoard[q], 0, 10);

					if (remain[k] > 0 && check(i, j, k)) {
						put(i, j, k);

						remain[k]--;
						dfs(i * 10 + j + 1, count + 1, left - k * k);
						remain[k]++;

						// 복원
						for (int q = 0; q < 10; q++)
							System.arraycopy(copyBoard[q], 0, board[q], 0, 10);
					}

				}

				return;
			}
		}
	}

	private static void put(int y, int x, int k) {

		for (int i = y; i < y + k; i++) {
			for (int j = x; j < x + k; j++) {
				board[i][j] = 2;
			}
		}
	}

	static boolean check(int y, int x, int k) {

		if (y + k - 1 >= 10 || x + k - 1 >= 10)
			return false;

		for (int i = y; i < y + k; i++) {
			for (int j = x; j < x + k; j++) {
				if (board[i][j] != 1)
					return false;
			}
		}

		return true;
	}
}