[백준] 색종이 붙이기 - Java

문제 출처

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

문제

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

예제 입력 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 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 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 0 0 0 0

예제 출력 1

0

예제 입력 2

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 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 0 0 0 0 0

예제 출력 2

4

예제 입력 3 

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 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 0 0 0 0 0

예제 출력 3

5

예제 입력 4

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 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 0 0 0 0 0

예제 출력 4

-1

예제 입력 5

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 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 0 0 0 0 0

예제 출력 5

7

예제 입력 6

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

예제 출력 6

4

예제 입력 7

0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

예제 출력 7

6

예제 입력 8

0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 0 0 0 0 1

예제 출력 8

5

풀이 방법

• 브루트포스를 이용해 풀이하였다.

1. 색종이 배열 (5장씩)을 생성하고, 색종이 배열 정보를 받는다
2. 5x5크기부터 시작하여, 붙일 수 있는 구간인지 판단하고 붙일 수 있으면 해당 지역을 0으로 교체 (dfs 끝나면 다시1 로 교체)한다.

• 위 두 가지 루틴을 메인으로 풀이를 하면 된다...

풀이 코드

package Baekjoon.색종이붙이기;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 김범규_색종이붙이기 {
    static int[][] board = new int[10][10];
    static int[] confetti = {0, 5, 5, 5, 5, 5};
    static int min = Integer.MAX_VALUE;

    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++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 0, 0);

        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }

    public static void dfs(int r, int c, int cnt){
        if(r >= 9 && c > 9){
            min = Math.min(min, cnt);
            return;
        }

        if(min <= cnt){
            return;
        }

        if(c > 9){
            dfs(r + 1, 0, cnt);
            return;
        }

        if(board[r][c] == 1){
            for(int i = 5; i >= 1; i--){
                //붙일수 있는 구간이면
                if(confetti[i] > 0 && checkArea(r, c, i)){
                    attach(r, c, i, 0);
                    confetti[i]--;
                    dfs(r, c + 1, cnt + 1);
                    attach(r, c, i, 1);
                    confetti[i]++;
                }
            }
        }
        else {
            dfs(r, c + 1, cnt);
        }
    }

    //붙이거나 떼기
    public static void attach(int r, int c, int size, int state){
        for(int i = r; i < r + size; i++){
            for(int j = c; j < c + size; j++){
                board[i][j] = state;
            }
        }
    }

    public static boolean checkArea(int r, int c, int size){
        if(r + size > 10 || c + size > 10){
            return false;
        }
        for(int i = r; i < r + size; i++){
            for(int j = c; j < c + size; j++){
                //범위안에 0이 있으면 탐색 종료
                if(board[i][j] != 1){
                    return false;
                }
            }
        }

        return true;
    }


}

결과

회고

• 범위 생각을 잘 못해서 >=가 아니라 >를 쓰다가 몇 번 틀렸다....