[백준]#17136 색종이 붙이기

SeungBird·2020년 8월 30일
1

⌨알고리즘(백준)

목록 보기
122/401

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

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

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

예제 입력 1

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1

0

예제 입력 2

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 2

4

예제 입력 3

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 3

5

예제 입력 4

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 4

-1

예제 입력 5

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 5

7

풀이

이 문제는 DFS 알고리즘을 이용해서 모든 경우의 수를 다 구해봐야 풀 수 있는 문제이다.

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

public class Main {
    static int[][] map = new int[10][10];
    static int min = Integer.MAX_VALUE;

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

        for(int i=0; i<10; i++) {
            String[] input = br.readLine().split(" ");
            for(int j=0; j<10; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        int[] papers = new int[6];
        dfs(0, papers);

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

    static void dfs(int row, int[] paper_used) {

        if(check()) {
            int cnt = 0;

            for(int i=1; i<=5 ; i++) {
                cnt += paper_used[i];
            }

            if(min > cnt)
                min = cnt;

            return;
        }

        for(int i=row; i<10; i++) {
            for(int j=0; j<10; j++) {
                if(map[i][j] == 1) {
                    for(int paper = 5 ; paper >= 1; paper--) {

                        if(paper_used[paper] < 5 && canAttach(i, j, paper)) {
                            paper_used[paper]++;
                            attach(i, j, paper);

                            dfs(i, paper_used);

                            recover(i, j, paper);
                            paper_used[paper]--;
                        }
                    }
                    return;
                }
            }
        }
    }

    static boolean canAttach(int x, int y, int paper) {

        for(int i=0; i<paper; i++) {
            for(int j=0; j<paper; j++) {

                if(!(x+i>=0 && x+i<10 && y+j>=0 && y+j<10))
                    return false;

                if(map[x+i][y+j] == 0)
                    return false;
            }
        }
        return true;
    }

    static void attach(int x, int y, int paper) {
        for(int i=0 ; i<paper; i++) {
            for(int j=0; j<paper; j++) {
                map[x+i][y+j] = 0;
            }
        }
    }

    static void recover(int x, int y, int paper) {
        for(int i=0; i<paper; i++) {
            for(int j=0; j<paper; j++) {
                map[x+i][y+j] = 1;
            }
        }
    }

    static boolean check() {
        for(int i=0; i<10; i++) {
            for(int j=0; j<10 ; j++) {
                if(map[i][j] == 1)
                    return false;
            }
        }
        return true;
    }
}
profile
👶🏻Jr. Programmer

0개의 댓글