[BaekJoon] 17136 색종이 붙이기 (Java)

1.  문제 링크

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

2.  문제

요약

• 정사각형 모양을 한 다섯 종류의 색종이가 있는데, 색종이의 크기는 1 x 1, 2 x 2, 3 x 3, 4 x 4, 5 x 5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있습니다.
• 색종이를 크기가 10 x 10인 종이 위에 붙이려고 하는데, 종이는 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸에는 0 또는 1이 적혀 있습니다.
• 0이 적힌 칸은 색종이가 있으면 안되며, 1이 적힌 칸은 모두 색종이 덮여져야만 합니다.
• 색종이를 붙일 때는 종이의 경계 밖으로 나가서도, 겹쳐도 안되며, 칸의 경계와 일치하게 붙여야 합니다.
• 종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구하는 문제입니다.
• 입력: 10개의 줄에 종이의 각 칸에 적힌 수가 주어집니다.
• 출력: 첫 번째 줄에 모든 1을 덮는데 필요한 색종이의 최소 개수를 출력합니다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력합니다.

3.  소스코드

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

public class Main {
    static final int SIZE = 10;
    static int[][] map;
    static int[] paperSize = {0, 5, 5, 5, 5, 5};
    static int answer;

    static void input() {
        Reader scanner = new Reader();
        map = new int[SIZE][SIZE];
        answer = Integer.MAX_VALUE;

        for(int row = 0; row < SIZE; row++) {
            for(int col = 0; col < SIZE; col++)
                map[row][col] = scanner.nextInt();
        }
    }

    static void solution() {
        dfs(0, 0, 0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    static void dfs(int x, int y, int count) {
        // 맨 끝 점에 도달 -> 정답 갱신
        if(x >= SIZE - 1 && y >= SIZE) {
            answer = Math.min(answer, count);
            return;
        }

        // count가 answer보다 크거나 같은 경우, 그 뒤에 색종이를 더 붙이면 어차피 답이 될 수 없음
        // 그러므로 끝냄
        if(answer <= count) return;

        // 아래 줄로 이동
        if(y > SIZE - 1) {
            dfs(x + 1, 0, count);
            return;
        }
        
        if(map[x][y] == 1) {
            for(int size = 5; size >= 1; size--) {
                if(paperSize[size] > 0 && isAttach(x, y, size)) {
                    attach(x, y, size, 0);
                    paperSize[size]--;
                    dfs(x, y + 1, count + 1);
                    attach(x, y, size, 1);
                    paperSize[size]++;
                }
            }
        } else {
            dfs(x, y + 1, count);
        }
    }

    static void attach(int x, int y, int size, int paper) {
        for(int row = x; row < x + size; row++) {
            for(int col = y; col < y + size; col++)
                map[row][col] = paper;
        }
    }

    static boolean isAttach(int x, int y, int size) {
        for(int row = x; row < x + size; row++) {
            for(int col = y; col < y + size; col++) {
                if(!isInMap(row, col)) return false;

                if(map[row][col] != 1) return false;
            }
        }

        return true;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < SIZE && y >= 0 && y < SIZE) return true;
        return false;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 첫 번째 행의 첫 번째 열부터 열을 우선으로 탐색하여 마지막 행의 마지막 열까지 DFS를 통해 모든 경우에 대해 색종이를 채워나갑니다.
  • 현재 탐색하고 있는 칸의 값이 1이라면 현재 탐색하고 있는 칸을 색종이를 붙이는 영역의 가장 왼쪽 위의 칸이라고 가정하고 5 x 5 크기의 색종이부터 1 x 1 크기의 색종이 순으로 색종이를 붙여봅니다.
    • 만약 현재 크기의 색종이가 아직 다 쓰이지 않았고 해당 영역에 현재 크기의 색종이를 붙일 수 있다면, 즉, 해당 영역의 모든 칸이 10 x 10 종이 안에 있고 모든 칸이 1이라면 현재 크기의 색종이를 붙이고 해당 색종이의 개수를 하나 줄입니다.
    • 붙인 후에 해당 열의 다음 칸을 기준으로 탐색을 진행합니다. 이 때, 3개의 파라미터를 전달하는데 다음 위치의 x, y 좌표, 현재까지 쓰인 색종이 개수를 전달합니다.
  • 만약 현재 탐색하고 있는 칸이 마지막 칸을 넘어섰다면 모든 영역에 색종이를 붙인 것이 되기 때문에 색종이 개수의 최솟값을 갱신하고 다음 경우를 살핍니다.
  • 만약 현재까지 사용한 색종이의 개수가 이전까지 10 x 10 종이에 색종이를 붙이는데 사용한 색종이의 개수의 최솟값보다 크다면 최솟값이 갱신되지 않기 때문에 해당 경우는 더이상 살피지 않고 다음 경우를 살핍니다.
  • 만약 현재 탐색하고 있는 칸이 가장 마지막 열에 도달했다면 다음 행으로 넘어갑니다.