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

문제 링크 : https://www.acmicpc.net/problem/17136

이 문제는 백트래킹을 이용하여 풀 수 있습니다. 이 문제는 문제에서 얘기한 조건을 차례대로 구현해나가면 풀 수 있습니다.

기본적인 탐색은 가로 방향으로 한 칸씩 진행하고, 끝 칸에 도착하면 아랫줄의 첫 칸부터 다시 진행합니다. 이 때 현재 위치가 0, 즉 색종이를 놓을 수 없는 곳이면 넘어갑니다.

만약 현재 위치가 1, 즉 색종이를 놓을 수 있는 곳이라면, 현재 보유 색종이 수에 따라 어느 정도 범위까지 차지하고 있는지를 확인합니다. 색종이 사용 순서는 가장 최소의 색종이 개수를 사용하므로 큰 순서대로 진행합니다. 이 때 현재 보유 색종이가 없으면 범위를 세지 않고 넘어갑니다.

색종이를 사용할 수 있는 범위에 덮을 수 있는 색종이가 있다면 색종이를 덮은 후 색종이를 덮은 다음의 가로값으로 넘어갑니다. 그 후 백트래킹으로 색종이를 풀고 다른 경우의 수를 진행합니다.

다음을 코드입니다. 주의할 점은 색종이를 놓아야 할 곳이 1이기 때문에 만약 색종이 배열과 체크 배열을 합쳐서 사용할 때 체크값과 색종이 배열의 값과 같이 생각하면 안됩니다. 체크가 안 된 곳이 1이다 라는 개념으로 접근하셔야 문제를 푸실 수 있습니다. 또한 색종이 내부 범위 설정 시 색종이 크기 + 현재 좌표 로 진행할 경우 그 수치는 색종이가 덮은 이후의 좌표값이 되므로 10을 포함하여 범위를 설정해주셔야 합니다.

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

public class Main{
    static int[][] req = new int[10][10];
    static int min = -1;

    // 색종이 사이즈를 인덱스, 인덱스 별 색종이 수 세팅
    static int[] squareCnt = {0,5,5,5,5,5};

    static boolean isSquare(int y, int x, int s){
        for(int i=0;i<s;i++){
            for(int j=0;j<s;j++){
                if(req[y+i][x+j]==0) return false;
            }
        }
        return true;
    }

    static void checkSquare(int y, int x, int s, int useSquare){
        if(useSquare==1) squareCnt[s]++;
        else squareCnt[s]--;

        for(int i=0;i<s;i++){
            for(int j=0;j<s;j++){
                req[y+i][x+j] = useSquare;
            }
        }
    }

    static void backtracking(int y, int x, int cnt){
        // 가로 방향 끝까지 돌았으면 한 칸 밑으로 다시 탐색
        if(x>9){
            backtracking(y+1,0,cnt);
            return;
        }

        // 세로 방향 끝까지 돌았으면 가장 최소의 값이 정답이 되도록 출력
        // 이 때 기본값은 -1 : 색종이를 모두 덮을 수 없는 경우
        if(y>9){
            if(min == -1) min = cnt;
            else if(min > cnt) min = cnt;
            return;
        }

        // 현재 위치에 색종이를 놓을 수 없으면 가로 방향으로 한 칸 가기
        if(req[y][x] == 0) {
            backtracking(y,x+1,cnt);
            return;
        }

        // 현재 보유 색종이 수만큼 반복문 돌기
        // 이 때 큰 색종이부터 덮는 것이 색종이를 가장 최소로 사용할 수 있는 방법
        for(int s=5;s>=1;s--){

            // 현재 보유 색종이가 없지 않거나 판 내부에 존재 시 실행
            // 이 때 y+s, x+s 값은 색종이 덮은 이후의 좌표값
            // 따라서 범위 설정 시 10까지는 허용
            if(squareCnt[s] != 0 && y+s<=10 && x+s<=10){

                // 만약 현재 덮을 수 있는 색종이 크기만큼 덮을 수 있다면
                if(isSquare(y,x,s)){

                    // 색종이를 덮음
                    checkSquare(y,x,s,0);

                    // 색종이 덮은 다음으로 진행
                    backtracking(y,x+s,cnt+1);

                    // 색종이 풀고 다른 경우의 수 진행
                    checkSquare(y,x,s,1);
                }
            }
        }
    }

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

        for(int i=0;i<10;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j=0;j<10;j++){
                req[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        backtracking(0,0,0);
        System.out.println(min);
    }

}