[백준] 17136번 : 색종이 붙이기 - 자바(JAVA)

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

17136번: 색종이 붙이기

 

문제 해석

다섯 종류의 색종이가 존재하고 각 종류의 색종이는 5개씩 가지고 있다 (총 25개)

색종이의 종류 5개

크기가 10 x 10인 종이 위에 붙이려고 한다

 

각각의 칸은 0 또는 1이 적혀 있고 1이 적힌 칸은 모두 색종이로 덮여야 한다.

 

0이 적힌 칸에는 색종이가 있으면 안된다.

 

색종이는 종이의 경계 밖으로 나가서는 안된다.

 

종이가 주어졌을 때 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

 

1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

 

 

문제 풀이 전 설계

색종이의 최소 개수를 구해야 합니다.

 

5x5를 붙이는 것보다 4x4 색종이를 여러 개 붙이는 경우가 더 답이 작을 수도 있습니다.

 

10 x 10 칸의 종이 위에 색종이를 붙이기 때문에 완전 탐색을 활용하여 해결하면 좋을 것 같습니다.

 

색종이를 최소로 사용하기 위해서는 5x5를 먼저 사용할수록 좋을 것 같습니다.

 

핵심 로직

1. papers 배열에 5,5,5,5,5를 저장 (종이의 최대 개수들)

2. DFS를 사용하여 백 트레킹

3. 좌표가 맨 끝에 도달한 경우 종이의 개수 반환

 

코드

import java.util.*;

public class Main_17136_색종이붙이기 {

    static int[][] board;
    static int min = Integer.MAX_VALUE;
    static final int SIZE = 10;
    static final int PAPER_COUNT = 5;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        board = new int[SIZE][SIZE];
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                board[i][j] = scan.nextInt();
            }
        }

        int[] remain = {0, PAPER_COUNT, PAPER_COUNT, PAPER_COUNT, PAPER_COUNT, PAPER_COUNT}; //각 색종이의 남은 개수를 표현한다.
        dfs(0, 0, remain, 0); //0,0부터 오른쪽 아래로 이동하며 색종이를 덮어 나간다.

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

    public static void dfs(int x, int y, int[] remain, int count) {
        if(x == SIZE-1 && y == SIZE) { //마지막에 도달했을때
            min = Math.min(min, count);
            return;
        }
        if(y == SIZE) { //오른쪽으로 이동하다가 범위를 벗어나면 아래로 이동
            dfs(x + 1, 0, remain, count);
            return;
        }
        if(count >= min) return; //현재 count가 최소값보다 크다면 더 이상 계산할 필요가 없다.

        if(board[x][y] == 1) {
            for(int j = 5; j >= 1; j--) {//제일 큰 색종이 사이즈 부터 붙일 수 있는지 확인한다.
                if(isAttach(x, y, j) && remain[j] > 0) { //색종이를 더 붙일 수 있다면 붙인다.
                    attach(x, y, j); //현재 위치에 j크기의 색종이를 붙여준다.
                    remain[j]--; //해당 색종이를 하나 사용하였으므로 감소시켜준다.
                    dfs(x, y + 1, remain, count + 1);
                    detach(x, y, j); //붙였던 색종이를 다시 떼어준다.
                    remain[j]++; //해당 색종이를 다시 떼어냈으므로 증가시켜준다.
                }
            }
        } else { //board[x][y]가 0인경우에는 오른쪽으로
            dfs(x, y + 1, remain, count);
        }
    }

    //x, y위치에서 부터 size만큼의 색종이를 붙이는 과정.
    public static void attach(int x, int y, int size) {
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                board[i][j] = 2; //색종이 붙였음을 표시
            }
        }
    }

    //x, y위치에서 부터 size만큼의 색종이를 떼는 과정.
    public static void detach(int x, int y, int size) {
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                board[i][j] = 1;
            }
        }
    }

    //x, y위치로 부터 size만큼의 색종이를 붙일 수 있는지 확인하는 과정.
    public static boolean isAttach(int x, int y, int size) {
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                if(i >= 10 || j >= 10) return false;
                if(board[i][j] != 1) return false;
            }
        }
        return true;
    }
}