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

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

17136번: 색종이 붙이기

풀이 후기

- 큰 종이를 먼저 붙이는 것은 그리디한 접근 방식이라고 할 수 있다. 하지만 언제나 큰 종이를 붙이는 건 예외가 존재하기 때문에 모든 경우를 탐색해야 한다.

- N-Queen문제가 생각났는데 가능하면 진행하고 불가능하면 다음 방법을 모색한다 => 백트래킹

- 처음에는 색종이를 붙이고 땔 때 과정을 복잡하게 생각했는데, 그냥 방문 표시 했다가 진행 후 다시 백 할때 방문 표시를 해제하는 순열처럼 생각하면 되었다.

- 그리고 색종이를 붙이고 떼는 메서드를 다르게 정의했었는데, state 값을 인자로 넘겨주면서 한 메서드로 처리할 수 있었다.

 

import java.util.*;

public class p17136 {
    static int min = 100;
    static int[][] map = new int[10][10];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        map = new int[10][10];
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                map[i][j] = sc.nextInt();
            }
        }

        solve(0, new int[6]);
        System.out.println(min==100? -1:min);
    }

    public static void solve(int idx, int[] cnt){
        if(idx==100){
            int sum = 0;
            for(int i=1;i<6;i++) sum += cnt[i];
            if(min > sum) min = sum;
            return;
        }

        int r = idx/10;
        int c = idx%10;
        if(map[r][c]==0) solve(idx+1, cnt);
        else{
            for(int i=5; i>0;i--){
                if(isPossible(r, c, i) && cnt[i]+1 <= 5) {
                    make(r, c, i, 0);
                    cnt[i]++;
                    solve(idx+1, cnt);

                    cnt[i]--;
                    make(r, c, i, 1);
                }
            }
        }

    }

    public static boolean isPossible(int r, int c, int size){
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                if((r+i>=10 || c+j>=10) || map[r + i][c + j] == 0)
                    return false;
            }
        }
        return true;
    }

    public static void make(int r, int c, int size, int state){
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                map[r+i][c+j] = state;
            }
        }
    }
}