BOJ - 색종이 붙이기

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

17136번: 색종이 붙이기

 

• 백트래킹 + 배열 조작 문제이다.
• 처음에는 각 DP 마다 모든 배열을 검사하도록 수행했더니 시간 초과가 나버렸다.
• 배열 검사는 가장 마지막에 오는 DP만 검사하여 조건에 맞는 색종이를 사용했는지 확인했다.

 

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //최소한으로 사용한 종이 개수
    private static int minUsedPaper = Integer.MAX_VALUE;

    //입력으로 주어진 맵 정보
    private static int[][] map = new int[10][10];

    //색종이
    private static int[] papers = new int[]{
            0, 5, 5, 5, 5, 5
    };

    public static void main(String[] args) throws IOException {
        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp(0, 0, 0);
        if (minUsedPaper == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(minUsedPaper);
        }
    }


    private static void dp(int y, int x, int usedPaper) {

        //모든 맵을 탐색함 경우 (9,9) -> (10, 0)
        if (y == 10 && x == 0) {
            if (isAllZero()) {
                minUsedPaper = Math.min(minUsedPaper, usedPaper);
                return;
            }
        }


        if (map[y][x] == 1) {
            for (int size = 0; size < 6; size++) {
                if (papers[size] == 0) continue;

                // 범위 체크 : 현 위치 + 색종이 사이즈
                if (y + size > 10 || x + size > 10) continue;

                // 색종이 사이즈로 덮을 수 있는지
                if (!isAvailableFill(y, x, size)) continue;

                //백트래킹
                setPaper(y, x, size, 0);
                papers[size] -= 1;
                if (x / 9 == 1) {
                    dp(y + 1, 0, usedPaper + 1);
                } else {
                    dp(y, x + 1, usedPaper + 1);
                }
                papers[size] += 1;
                setPaper(y, x, size, 1);
            }
        } else {
            if (x / 9 == 1) {
                dp(y + 1, 0, usedPaper);
            } else {
                dp(y, x + 1, usedPaper);
            }
        }
    }

    private static void setPaper(int y, int x, int size, int flag) {
        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                map[i][j] = flag;
            }
        }
    }

    private static boolean isAvailableFill(int y, int x, int size) {
        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                if (map[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    //디버깅용
    private static void printMap() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                builder.append(map[i][j] + " ");
            }
            builder.append("\n");
        }

        System.out.println(builder);
    }

    private static boolean isAllZero() {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (map[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}