BOJ17136_색종이 붙이기

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

문제정리

1. 색종이의 크기가 1*1 , 2*2 , 3*3 , 4*4 , 5*5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

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

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

4. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

문제issue

1. 재귀를 이용한다.

해결흐름

1. map을 입력 받을 때 1의 위치를 list에 저장한다.

2. 재귀

(1) 종료조건 : 모든 1을 살펴보았다. idx가 list의 크기와 같다.

(2) 가지고 다닐 값 : 1 위치를 가지고 있는 list , 색종이 몇장 사용?cnt

(3) 복귀 시켜야 할 값 : 변경한 map , 사용한 색종이 다시++

(4) 갱신 , 재귀 : 색종이를 붙일 수 있으면 색종이를 몇장 사용했는지 갱신해서 재귀

갱신x , 재귀 : map이 1이 아니라면 인덱스만 증가해서 재귀

(5) 가지치기 : 최솟값을 구하는 경우 중간에 현재 가장 작은 값보다 cnt가 커지면 더 이상 볼필요 없다.

3. 색종이를 붙일 수 있는지 확인

(1) check()에다가 현재의 1의 위치와 어떤 크기의 색종이를 사용했는지 넘겨준다.

(2) 그 크기의 색종이가 더이상 없으면 return false

(3) 그 크기의 색종이가 있지만 현재 1의 위치에서 색종이의 크기 만큼 검사하면서 중간에 1이 아니면 색종이 설치가 불가능하다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    static class pair {
        int r;
        int c;
 
        public pair(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
 
    private static int min_paper;
    private static int[][] map;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[10][10];
        List<pair> list = new ArrayList<pair>();
        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            for (int j = 0; j < 10; j++) {
                int number = Integer.parseInt(st.nextToken());
                map[i][j] = number;
                if (number == 1) {
                    list.add(new pair(i, j));
                }
            }
        }
        min_paper = Integer.MAX_VALUE;
        dfs(list, 0, 0); // list , idx , paper_cnt
        if(min_paper == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(min_paper);
    } // end of main
 
    private static int[] paper = { 0, 5, 5, 5, 5, 5 };
 
    private static void dfs(List<pair> list, int idx, int paper_cnt) {
        // 가지치기
        if(min_paper < paper_cnt)
            return;
        // 종료조건
        if (idx == list.size()) {
            if (min_paper > paper_cnt)
                min_paper = paper_cnt;
            return;
        }
        pair p = list.get(idx);
        if (map[p.r][p.c] == 0) {
            dfs(list, idx + 1, paper_cnt); // paper_cnt 갱신없이 재귀
        }
        for (int i = 5; i >= 1; i--) {
            // check에는 붙어야 하는 색종이 위치 , 어떤 크기의 색종이?
            if (check(p, i)) {
                // 색종이 사용
                paper[i]--;
                // 색종이 붙여
                for (int j = p.r; j < p.r + i; j++) {
                    for (int k = p.c; k < p.c + i; k++) {
                        map[j][k] = 0;
                    }
                }
                // 갱신해서 재귀
                dfs(list, idx + 1, paper_cnt + 1);
                paper[i]++;
                for (int j = p.r; j < p.r + i; j++) {
                    for (int k = p.c; k < p.c + i; k++) {
                        map[j][k] = 1;
                    }
                }
            }
        }
    }
 
    private static boolean check(pair p, int paper_number) {
        // 해당 색종이 없으면 못 붙임
        if(paper[paper_number] <= 0) {
            return false;
        }
        int r = p.r;
        int c = p.c;
        boolean flag = false;
        here: for (int i = r; i < r + paper_number; i++) {
            for (int j = c; j < c + paper_number; j++) {
                if (i >= 0 && i < 10 && j >= 0 && j < 10) {
                    // 맨 끝부분이고 거기까지 1이면 색종이 붙일 수 있음
                    if (i == r + paper_number - 1 && j == c + paper_number - 1 && map[i][j] == 1) {
                        flag = true;
                        break here;
                    } else if (map[i][j] != 1) { // 중간에 1이 아니면 그 색종이 붙일 수 없음
                        flag = false;
                        break here;
                    }
                }
            }
        }
        return flag;
    }
} // end of class