[백준_17136] 색종이 붙이기.java

목차

1. 문제 파악하기
2. 해법 설계
3. 코드 구현
4. 디버깅

 

---

문제 파악하기

주어진 10 X 10 크기의 종이에 대한 정보가 주어진다.

종이에는 길이가 1부터 5까지의 정사각형 색종이를 이용하여 붙이려고 한다.

 

각 종이는 5개씩 존재하며, 가장 적은 개수의 색종이로 종이를 모두 채워라.

 

---

해법 설계 과정

색종이의 길이가 큰 거부터 작은 순으로 돌아가며 덮을 수 있는 거 찾으면서 전부 돌기
1까지 다 돌았는데 paper내의 1이 하나라도 남아있으면 바로 -1

1 1 1 1 1 1    0 0 0 0 0 1
1 1 1 1 1 1 -> 0 0 0 0 0 1
1 1 1 1 1 1    0 0 0 0 0 1
1 1 1 1 1 1    0 0 0 0 0 1

--> 반례 발생, 풀이 설계 방법 전환

알고리즘을 사용해서 누가 뭐래도 최소값이라고 말할 수 있도록 해야해!
--> '1'을 마주쳤을 때마다 길이 5의 색종이에서 1까지 모든 색종이들의 부착 경우들을 조사하고 
이를 저장해서 각각의 정보를 담고 있는 상태에서 나뭇가지 뻗어나가 듯이 조사하면 되겠다!!
(백트래킹)


!!유레카!!
1을 발견했어?? 그럼 5에서 1까지 각 색종이들의 모든 경우에 대한 평행 세계로 보내버리자..
그러면 각각의 크기에 대한 모든 경우들을 다 저장하고 갈테니까 결국에는 최소값을 구할 수 있을거야!

 

 

---

💻코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 다시다시다시색종이붙이기 {
    static int[] confetti;
    static int confettiCnt;
    static boolean[][] paper; //붙이려는 종이
    private static int minCnt;

    /*
    색종이 큰 거부터 작은 순으로 덮을 수 있는 거 찾으면서 전부 돌기
    1까지 다 돌았는데 paper내의 1이 하나라도 남아있으면 바로 -1
    --> 이게 아니구나..

    알고리즘을 사용해서 누가 뭐래도 최소값이라고 말할 수 있는 방법을 탐색하자!
    -->백트래킹 방식을 쓴다고 했을 때, 주어진 입력값에서 될 수 있는 경우들을 다 해봐야 할 텐데
    이걸 어떤 방식으로 분리하고 나눌 수 있을까..

    !!유레카!!
    1을 발견했어?? 그럼 모든 경우에 대해서 wifi( 평행 세계 )로 보내버리자..
    그러면 각각의 크기에 대한 모든 경우들을 다 저장하고 갈테니까 결국에는 최소값을 구할 수 있을거야!
    --> 백트래킹 + DFS
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        paper = new boolean[10][10];
        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                if (Integer.parseInt(st.nextToken()) == 1)
                    paper[i][j] = true;
            }
        } //종이 입력받기
        minCnt = 987654321;
        confettiCnt = 0;
        confetti = new int[6];
        for(int i = 1; i<=5; i++)
            confetti[i] = 5;

        backtracking(0,0,confettiCnt,confetti);

        if(minCnt == 987654321) {
            System.out.println(-1);
            return;
        }
        System.out.println(minCnt);
    }

    public static void backtracking (int n, int r, int confettiCnt, int[] confetti){
        if(n >= 9 && r> 9) { //탐색 끝!
            if (isPossible()) {
                if (confettiCnt < minCnt)
                    minCnt = confettiCnt;
            }
            return;
        }
        if(confettiCnt >= minCnt ) return; //최소기대값보다 커지면 이건 뭐, 탐색 필요가 없지!
        if( r > 9 ) {
            backtracking(n+1,0,confettiCnt, confetti);
            return;
        }

        if (paper[n][r]) { //둘 수 있어?!
            for (int i = 5; i >= 0; i--) { //마주칠 때마다 우리 모든 색종이의 가능성을 열어두자고
                if (tapePossible(n, r, i, confetti)) { //이 종이크기로도 붙일 수 있어?
                    tape(n, r, i); //자자 붙입니다
                    backtracking(n, r + 1, confettiCnt + 1, confetti); //이제 너는 너만의 길을 가!
                    takeoff(n, r, i); //붙인 거 다시 뗍니다~~
                }
            }
        }
        else backtracking(n, r + 1, confettiCnt,confetti);//다음 거 조사하자!
    }

    public static boolean isPossible(){
        for(int i = 0 ; i<10; i++){
            for(int j = 0 ; j<10 ; j ++){
                if(paper[i][j]) return false;
            }
        }
        return true;
    }
    public static boolean tapePossible(int m ,int n,int x, int[] confetti ){

        if(confetti[x] == 0 ) return false; //색종이가 없는데요..그럼 나가!

        for(int k = 0 ; k<x;k++){
            for(int l = 0;l<x;l++) {
                if (m + k >= 10 || n + l >= 10) return false; //범위 넘어가면 나가
                if (!paper[m + k][n + l]) return false; //거짓부렁이도 나가
            }
        }
        return true;
    }
    private static void tape(int m, int n, int x){
        for(int k = 0; k<x;k++) {
            for (int l = 0; l < x; l++) {
                paper[m + k][n + l] = false;
            }
        }
        confetti[x]--;
    }
    private static void takeoff(int m, int n, int x){
        for(int k = 0; k<x;k++) {
            for (int l = 0; l < x; l++) {
                paper[m + k][n + l] = true;
            }
        }
       confetti[x]++;
    }
}