[BOJ] 백준 17136번 : 색종이 붙이기 (JAVA)

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

17136번: 색종이 붙이기

문제

<그림 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을 출력한다.

 

풀이

DFS와 백트래킹을 활용하여 완전 탐색을 수행하면 풀리는 문제였습니다. 저는 처음에 그리디적인 방식으로 접근하였으나, 무조건 큰 색종이부터 붙이는 것보다  하나 작은 크기가 4x4인 색종이로 여러 개 붙이는 경우가 더 답이 작을 수도 있다는 것을 깨닫고 다른 방식을 생각하였습니다.

그렇게 생각해낸 것이 순열이었습니다. 5P5 = 120가지의 순열을 생성하여 5개의 수에 대하여 순서를 정해주었습니다. 하지만, 여기서도 반례가 존재하였습니다. 

 

 

이러한 예제가 있다고 가정해 봅시다. 저의 로직에 경우, 3x3 색종이를 먼저 붙일 수 있으므로 될 수 있는 색종이를 연속적으로 2개 붙일 것입니다. 따라서 아래와 같은 모습이 됩니다.

 

 

그리고 2x2 색종이를 붙일 수 있으므로 연속적으로 1개 붙일 것입니다.

 

 

그리고 나머지는 1x1 색종이로 붙일 수 있으므로 결과적으로 답은 7이 나옵니다.

 

 

하지만, 실제 답은 7이 아니라 4입니다. 3x3 색종이를 연속으로 붙이는 것이 아니라, 3x3 색종이를 붙이고 가운데 2x2 색종이를 2개 붙이고, 오른쪽에 3x3 색종이를 붙이면 4개만으로도 모든 1을 덮을 수 있게 됩니다.

 

 

그렇다면, 우리는 어떠한 로직을 사용해야할까요?

바로 큰 종이부터 붙이는 그리디적인 사고를 이용하되, DFS와 백트래킹을 사용함으로써 완전탐색을 수행해야합니다. 일단, nxn 범위 내에 모두 1이 존재한다면 nxn 색종이를 붙였다가 뗐다가 반복하는 식입니다.

전체적인 로직은 다음과 같습니다.

1. paper 배열에 5, 5, 5, 5, 5를 저장한다. (종이의 최대 개수)

2. DFS를 사용하여 백트래킹을 시도. 

3. 좌표가 맨 끝에 도달하였을 경우, 지금까지 붙인 종이의 개수를 반환한다.

 

2번에 해당하는 내용은 아래 코드의 주석을 참고하시면서 리딩을 해 주시면 좋을 것 같습니다.

 

아래는 위 풀이를 이용하여 작성한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] map;
    static int[] paper = { 0, 5, 5, 5, 5, 5 };
    static int ans = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        map = new int[10][10];
        for (int i = 0; i < map.length; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < map[i].length; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        DFS(0, 0, 0);
 
        if (ans == Integer.MAX_VALUE) {
            ans = -1;
        }
 
        bw.write(ans + "\n");
        bw.close();
        br.close();
    }
    
    // DFS + 백트래킹
    public static void DFS(int x, int y, int cnt) {
        // 맨 끝점에 도달하였을 경우, ans와 cnt 비교하고 종료.
        if (x >= 9 && y > 9) {
            ans = Math.min(ans, cnt);
            return;
        }
 
        // 최솟값을 구해야하는데 ans보다 cnt가 커지는 순간
        // 더 이상 탐색할 필요가 없어짐.
        if (ans <= cnt) {
            return;
        }
 
        // 아래 줄로 이동.
        if (y > 9) {
            DFS(x + 1, 0, cnt);
            return;
        }
 
        if (map[x][y] == 1) {
            for (int i = 5; i >= 1; i--) {
                if (paper[i] > 0 && isAttach(x, y, i)) {
                    attach(x, y, i, 0); // 색종이를 붙임.
                    paper[i]--;
                    DFS(x, y + 1, cnt + 1);
                    attach(x, y, i, 1); // 색종이를 다시 뗌.
                    paper[i]++;
                }
            }
        } else { // 오른쪽으로 이동.
            DFS(x, y + 1, cnt);
        }
    }
 
    // 색종이를 붙이는 함수.
    public static void attach(int x, int y, int size, int state) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                map[i][j] = state;
            }
        }
    }
 
    // 색종이를 붙일 수 있는지 확인.
    public static boolean isAttach(int x, int y, int size) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (i < 0 || i >= 10 || j < 0 || j >= 10) {
                    return false;
                }
 
                if (map[i][j] != 1) {
                    return false;
                }
            }
        }
        return true;
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.