[BOJ] 백준 [17136] 색종이붙이기 JAVA

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

17136번: 색종이 붙이기

📝문제

📝풀이

이 문제의 핵심은 그리디하게 접근해서는 풀 수 없는 문제이다.

반례)
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 0 0
0 0 1 1 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

답은 4인데, 큰 것 부터 차례대로 붙이면 4보다 많은 갯수가 나온다.
따라서 완전탐색을 진행해야한다.

1. 주어진 좌표에서 1 찾기
2. 해당 좌표(top-left) 기준으로 사이즈마다 모두 가능한지 검사하기
3. 2번이 가능하다면 해당 좌표를 -1로 두고 1번을 반복(dfs) 
4. 3번의 과정이 끝이나면 백트래킹

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.util.Arrays.stream;


public class Main {

    static int[][] map = new int[10][10];
    static int[] arr = new int[6];
    static int min = 26;

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

        for(int i=0;i<10;i++){
            map[i] = stream(br.readLine().split(" "))
                                .mapToInt(Integer::parseInt)
                                .toArray();
        }
        Arrays.fill(arr,5);
        arr[0]=0;

        dfs();

        System.out.println(min>25?-1:min);
    }

    private static void dfs() {

        int[] point = find();

        if(point[0] == -1 && point[1]==-1){ // 최소값 갱신 or 종결조건:탐색 끝좌표
            int cnt = 25 - stream(arr).sum();
            min = Math.min(min, cnt);
            return;
        }

        int x = point[0];
        int y = point[1];


        for (int size = 5; size >= 1; size--) {
            if (arr[size] > 0 && canAttach(x, y, size)) {
                attach(x, y, size); //붙이기
                dfs();
                attach(x, y, size); //떼기
            }
        }

    }

    private static int[] find() { // 좌표찾기

        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                if(map[i][j]==1)
                    return new int[]{j,i};
            }
        }
        return new int[]{-1,-1};
    }

    private static void attach(int x, int y, int size) {
        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                map[i][j]*=-1;
            }
        }

        arr[size] += map[y][x];
    }

    private static boolean canAttach(int x, int y, int size) {
        for(int i=y;i<y+size;i++){
            for(int j=x;j<x+size;j++){
                if(!isRange(j,i) || map[i][j]!=1) // 0: 못붙이는자리 -1: 이미 붙여진 자리
                    return false;
            }
        }
        return true;
    }

    private static boolean isRange(int x, int y) {
        return x>=0&&y>=0&&x<10&&y<10;
    }
}