[백준] 색종이 붙이기

https://www.acmicpc.net/problem/17136

문제 요약

10 x 10 크기에 색종이를 최소 개수로 붙여야 한다.

생각

• 범위가 충분히 작기에 브루트포스 방식으로 접근한다.
• 색종이가 1x1 ~ 5x5가 있고 최소 개수가 되기 위해 그리디스럽게 5x5로 먼저 접근해도 되겠다고 생각한다.
• 브루트포스로 접근하여 모든 색종이를 다 붙여보지만 붙일 수 없는 경우라면 더 보지 않고 return 하는 게 낫다

어떤 경우일까

• 일단 붙이는 좌표 기준으로 색종이 범위가 벗어나면 붙일 수 없다
• 색종이가 크기 당 각 5개씩 있으므로 어떤 색종이를 다 썼다면 붙일 수 없다 -> 다음 색종이 사용해야한다
• 색종이를 붙이려고 하는데 기존에 사용한 색종이 개수(1을 모두 채운)보다 더 많이 사용했다며 볼 필요 없다

재귀를 사용할 때 func() 의 인자를 어떻게 잡아야 할까

• 색종이를 붙이는 위치가 필요하니깐 위치 의미하는 파라미터
• 현재까지 사용한 색종이 개수를 알아야 하는 파라미터
  -> func(loc, cnt)

색종이를 붙였다면 그 자리는 어떻게 처리할까

1 부분에 색종이를 붙이는 것이기에 붙였다면 그 사이즈만큼 0으로 처리해서 더 이상 보지 않는다
java fill(n, m, i, 0); // 1을 0으로 채우기
당연스럽게도 0으로 채운 부분은 다음 턴 때 다시 봐야 하기에 1로 복구 시켜야한다.

코드

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

public class Main{

    public static int[][] board = new int[12][12];
    public static int[] paperCount = {0, 5, 5, 5, 5, 5};
    public static int res = Integer.MAX_VALUE;


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;

        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());
            }
        }

        func(0, 0);
        if(res == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(res);

    }

    private static void func(int loc, int cnt) {

        if (loc == 100) {
            res = Math.min(res, cnt);
            return;
        }

        if (res <= cnt) return;

        int n = loc % 10;
        int m = loc / 10;

        if(board[n][m] == 1) {

            for(int i = 5; i >= 1; i--) {
                if(paperCount[i] > 0 && check(n, m, i)) {
                    paperCount[i]--;
                    fill(n, m, i, 0); // 1을 0으로 채우기
                    func(n * m + 1, cnt + 1);

                    fill(n, m, i, 1); // 0으로 채웠던 부분 다시 1로 복구
                    paperCount[i]++;

                }
            }
        } else {
            func(loc + 1, cnt);
        }

    }

    private static boolean check(int n, int m, int num) {

        if(n + num > 10 || m + num > 10) return false;

        for (int i = n; i < n + num; i++) {
            for (int j = m; j < m + num ; j++) {
                if(board[i][j] == 0) return false;
            }
        }

        return true;
    }

    private static void fill(int n, int m, int num, int k) {

        for(int i = n; i < n + num; i++) {
            for(int j = m; j < m + num; j++) {
                board[i][j] = k;
            }
        }
    }
}