백준 17136 색종이 붙이기 Java

삼성 기출문제인 색종이 붙이기 문제이다.

삼성 기출 문제는 거의 대부분 완전 탐색을 해야 하는구나 하고 느꼈다.

 

이 문제는 색종이 크기가 큰 순부터 붙이는 그리디적인 요소와

DFS + 백트래킹을 활용해서 풀어야 한다.

 

꽤 오랜시간 못 맞추고 여러 번 틀렸었는데

해답을 보고 나서야 순서가 틀렸구나 하고 깨달았다.

 

나는 색종이 크기가 큰 순서대로해서 색종이 크기를 기준으로

배열을 돌면서 색종이를 붙이는 방식으로 구현했다.

이 방식이 안돼서 색종이의 크기를 1, 2->1, 3->2->1... 이런 식으로도 구현했었다.

하지만 이렇게하면 색종이를 붙일 수 있는 모든 경우의 수를 탐색할 수 없다.

 

색종이를 붙이는 모든 경우를 탐색하기 위해선

배열을 기준으로 색종이 크기를 큰 순서대로 돌면서

색종이를 붙이는 방식으로 구현해야 한다.

 

DFS를 하는 도중에 전에 저장된 최소값보다 색종이의 사용 수가 크면 

종료시켜주는 게 빠르다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q17136 {
    static int [][] a = new int[10][10];
    static int [] coloredPaper = {0, 5, 5, 5, 5, 5};
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        for(int i=0; i<10; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            for(int j=0; j<10; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0);
        System.out.println(ans==Integer.MAX_VALUE ? -1 : ans);
    }
    public static void dfs(int idx, int cnt) {
        if(idx == 100) { 
            ans = Math.min(ans, cnt);
            return;
        }
        if(ans <= cnt) return;
        int r = idx/10;
        int c = idx%10;
        if(a[r][c] == 1) {
            for(int i=5; i>0; i--) {
                if(coloredPaper[i] > 0) {
                    if(check(r, c, i)) {
                        fill(r, c, i, 0);
                        coloredPaper[i]--;
                        dfs(idx+1, cnt+1);
                        fill(r, c, i, 1);
                        coloredPaper[i]++;
                    }
                }
            }
        } else {
            dfs(idx+1, cnt);
        }
    }
    public static boolean check(int r, int c, int size) {
        if(r+size>10 || c+size>10) return false;
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) {
                if(a[r+i][c+j] != 1) return false;
            }
        }
        return true;
    }
    public static void fill(int r, int c, int size, int state) {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) {
                a[r+i][c+j] = state;
            }
        }
    }
}