[ 백준 17136 ] 색종이 붙이기 ( 자바 )

[ 백준 17136 ] 색종이 붙이기 ( java )

 

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

 

 

 

출처: 백준 코딩 테스트 연습, https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

 

 

 

핵심 

1 dfs

dfs는 지도를 탐색하다 1이 나오면 크기 1~5 종이로 덮고, 다음 dfs를 부른다. 

만약 덮지 못하면 종료. 

모든 1을 덮었다면 사용한 종이 비교 후 종료

 

이 때, 

1 의미: 덮어야 위치 

0 의미: 덮지 말아야 하며, 이미 색종이가 붙여있을 수 있다. 

 

( 바보같이 색종이 5개 세는 곳에서 <, <= 차이로 틀렸었는데 테스트케이스는 통과 됐었다. )

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st;
        for(int i = 0 ; i < 10 ; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < 10 ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int[] use =  new int[5];
        dfs(0, use);
        if(min == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(min);
        
    }
    static int[][] map = new int[10][10];
    
    static int min = Integer.MAX_VALUE;
    static void dfs(int y, int[] use) {
        
        if(allCover()) {
            
            int cnt = 0;
            for(int i = 0 ; i < 5 ; i++) {
                cnt += use[i];
            }
            if(min > cnt)
                min = cnt;
            return;
        }
 
        for(int i = y ; i < 10 ; i++) {
            for(int j = 0 ; j < 10 ; j++) {
                if(map[i][j] == 1) {
                    for(int paper = 4 ; paper >=0 ; paper-- ) {
                        if(use[paper] < 5 && canCover(i, j, paper)) {
                            use[paper]++;
                            cover(i, j, paper);
                            dfs(i, use);
                            uncover(i, j, paper);
                            use[paper]--;
                        }
                    }
                    return;
                }
            }
        }
    }
    
    // 1인 부분만 덮어야 한다. 0이 있다면 덮지 못 함. 
    static boolean canCover(int y, int x, int delta) {
        int ny, nx;
        for(int dy = 0 ; dy <= delta ; dy++) {
            for(int dx = 0 ; dx <= delta; dx++) {
                ny = y + dy;
                nx = x + dx;
                if(!(ny>=0 && ny < 10 && nx >= 0 && nx < 10))
                    return false;
                if(map[ny][nx] == 0)
                    return false;
            }
        }
        return true;
    }
 
    static void cover(int y, int x, int delta) {
        int ny, nx;
        for(int dy = 0 ; dy <= delta ; dy++) {
            for(int dx = 0 ; dx <= delta; dx++) {
                ny = y + dy;
                nx = x + dx;
                map[ny][nx] = 0;
            }
        }
    }
    
    static void uncover(int y, int x, int delta) {
        int ny, nx;
        for(int dy = 0 ; dy <= delta ; dy++) {
            for(int dx = 0 ; dx <= delta; dx++) {
                ny = y + dy;
                nx = x + dx;
                map[ny][nx] = 1;
            }
        }
    }
    
    static boolean allCover() {
        for(int i = 0 ; i < 10 ; i++) {
            for(int j = 0 ; j < 10 ; j++) {
                if(map[i][j] == 1)
                    return false;
            }
        }
        return true;
    }
}