[백준] 17136: 색종이 붙이기 (DFS, 백트래킹, Brute-force) - JAVA

# 문제

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

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

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

 

 

# 예제

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

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

 

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

5

 

# 필요개념

처음에는 BFS를 이용해서 풀까 했는데, 가장 큰 종이로 덮는 경우 예외도 있고, 코드가 너무~!!!! 복잡해져서 그냥 brute force로 풀기로 했다. 모든 경우를 탐색해야 하니까 DFS도 함께 이용해주었다.

 

따지는 것은 큰 사이즈의 종이부터 넣었고 ans을 작은 값으로 갱신하면서 가지치기를 해나갔다. 사용하는 종이의 개수가 가장 작은 경우를 출력해야 하기 때문에, 종이의 개수가 최소값보다 커지는 경우에는 그 뒤를 따지지 않고 경우의 수를 제거했다.

 

색종이로 모두 채워졌는지 확인

사용하는 종이의 수를 인자로 받아서 ans와 비교 후 ans보다 큰 경우에는 굳이 따지지 않고 반환했다.

이후 모든 배열을 순회하면서 안 채워진 부분이 있는지 확인하고 없으면 ans를 갱신해주었다.

안 채워진 부분이 생기면 그 부분에 종이를 붙이는 explore 함수를 호출한다.

 

 

종이 사이즈 별로 넣어보기

종이 크기가 1~5로 5개 뿐이라서 한개씩 넣어보았다. 채워질 수 있는 경우에는 채우고, 채운 종이를 1만큼 빼서 사용했다는 것을 표시한다. 그 후 위 함수를 재귀로 호출해주었다.

이후에는 채운 것을 원상복구 시켜서 로직이 꼬이지 않도록 했다.

 

종이 채우기, 복구시키기, 채울 수 있는지 확인하기

fill과 unfill은 파라미터로 넘긴 값으로 채우면 하나의 함수로 통일할 수 있긴 하지만,,,,, 가독성을 위해서 나눴다

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static boolean[][] maps;
    static int[] papers = new int[]{0, 5, 5, 5, 5, 5};
    private static final int SIZE = 10;
    private static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        fillMaps();
        calculator(0);
        if (ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }

    private static void calculator(int usedPaper) {
        if (usedPaper >= ans) return;

        int y = -1;
        int x = -1;
        for (int i = 0 ; i < SIZE ; i++) {
            for (int j = 0 ; j < SIZE ; j++) {
                if (maps[i][j]) {
                    y = i;
                    x = j;
                    break;
                }
            }
            if (y != -1) break;
        }

        if (y == -1) {
            ans = Math.min(ans, usedPaper);
            return;
        }

        explore(y, x, usedPaper);
    }

    private static void explore(int y, int x, int usedPaper) {
        for (int i = 5 ; i >= 1 ; i--) {
            if (papers[i] > 0) {
                if (checkFill(y, x, i)) {
                    fill(y, x, i);
                    papers[i]--;
                    calculator(usedPaper + 1);
                    unfill(y, x, i);
                    papers[i]++;
                }
            }
        }
    }


    private static void fill(int y, int x, int size) {
        for (int i = y ; i < y + size ; i++) {
            for (int j = x ; j < x + size ; j++) {
                maps[i][j] = false;
            }
        }
    }

    private static void unfill(int y, int x, int size) {
        for (int i = y ; i < y + size ; i++) {
            for (int j = x ; j < x + size ; j++) {
                maps[i][j] = true;
            }
        }
    }


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

    private static void fillMaps() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        maps = new boolean[SIZE][SIZE];
        for (int i = 0 ; i < SIZE ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0 ; j < SIZE ; j++) {
                maps[i][j] = (Integer.parseInt(st.nextToken()) == 1);
            }
        }
    }
}

 

# 결과