[BOJ] 17136 색종이 붙이기 - JAVA

📚 Problem

17136 색종이 붙이기

📝 Solution

• 한변의 크기가 1~5인 정사각형 각각 5개
• 10X10 크기의 정사각형 종이에 붙이기
• 1이 적힌 칸은 종이가 덮여져야함
• 0이 적힌 칸은 종이 X
• 붙이는 종이가 범위를 벗어나거나 겹치면 X
• 모든칸을 붙이는데 필요한 종이의 최소 개수 구하기
• 못붙이면 -1

Key Idea

• (0, 0)부터 움직이면서 만약 칸의 숫자가 1이라면,
• 크기가 5인 색종이부터 1인 색종이를 차례로 검사하며
• 붙일 수 있다면 종이를 붙이고 칸의 숫자를 0으로 바꿔줍니다

• size 크기의 색종이를 붙일 수 있는지 확인하는 함수
• 범위를 벗어나거나 0이 있으면 붙일수 없으므로 false

    private static boolean canAttach(int x, int y, int size){
        for(int i = x; i < x + size; i++)
            for(int j = y; j < y + size; j++){
                if(i > 9 || j > 9)
                    return false;
                if(board[i][j] != 1)
                    return false;
            }
        return true;
    }

• state = 0 이면 색종이를 board 위에 붙이는 것
• state = 1 이면 색종이를 board 에서 다시 떼어내는 것

    private static void attach(int x, int y, int size, int state){
        for(int i = x; i < x + size; i++)
            for(int j = y; j < y + size; j++)
                board[i][j] = state;
    }

💻 Code

import java.util.Scanner;

public class Main {
    private static int min = Integer.MAX_VALUE;
    private static int[] papers = {0, 5, 5, 5, 5, 5};
    private static int[][] board = new int[10][10];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        for(int i = 0; i < 10; i++)
            for(int j = 0; j < 10; j++)
                board[i][j] = scanner.nextInt();

        DFS(0, 0, 0);

        if(min == Integer.MAX_VALUE)
            min = -1;

        System.out.println(min);

        scanner.close();
    }

    private static void attach(int x, int y, int size, int state){
        for(int i = x; i < x + size; i++)
            for(int j = y; j < y + size; j++)
                board[i][j] = state;
    }

    private static boolean canAttach(int x, int y, int size){
        for(int i = x; i < x + size; i++)
            for(int j = y; j < y + size; j++){
                if(i > 9 || j > 9)
                    return false;
                if(board[i][j] != 1)
                    return false;
            }
        return true;
    }

    private static void DFS(int x, int y, int count){
        if(x == 9 && y > 9){
            min = Math.min(min, count);
            return;
        }

        if(count > min)
            return;

        if(y > 9){
            DFS(x + 1, 0, count);
            return;
        }

        if(board[x][y] == 1){
            for(int size = 5; size >= 1; size--)
                if(papers[size] > 0 && canAttach(x, y, size)){
                    papers[size]--;
                    attach(x, y, size, 0);
                    DFS(x, y + 1, count + 1);
                    attach(x, y, size, 1);
                    papers[size]++;
                }
        }
        else
            DFS(x, y + 1, count);
    }
}