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

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

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

풀이

완전 탐색을 통해서 풀어야 하는 구현 문제이다.

 

이번 문제는 풀고나니 어렵지 않았는데 구현하면서 생각해 줘야 하는 조건들을 놓쳐 다시 구현하느라 시간이 오래 걸렸다. 구현 문제는 꼭꼭 문제를 정확히 읽고 조건을 하나라도 빠트리지 않는 것이 가장 중요하다!

 

탐색 방향은 오른쪽 아래로만 확인하면 되므로 탐색할 때 x, y좌표 값에 따라 이동 방향을 지정해 주었다. 예를 들어 현재y값이 10(범위를 벗어남)이라면 다음 탐색 위치를 x  = x + 1, y = 0으로 다음 줄을 탐색하도록 해주었다.

 

그리고 색종이를 한번 붙이고 나서 해당 값이 최소 값이 아니라면 다시 색종이를 떼어주는 작업이 필요했다. 색종이를 붙이기 전에 먼저 해당 크기의 색종이를 붙일 수 있는지 확인한 후 붙이도록 해 주었다. 

 

색종이의 남은 개수는 remain 배열을 만들어서 관리해주었다. 

 

시간을 많이 빼앗긴 부분은 종료 조건 부분이었다..! 마지막 도달했을때의 조건을 (x == 10 && y == 10)으로 해주면 x가 10일때도 탐색을 하기 때문에 ArrayIndexOutOfBoundsException이 발생했다. 조건을 따라가 보며 마지막이 되는 값을 확인해보니 x가 9이고 y가 10일때였다.

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

board에서 가장 마지막을 탐색하는 경우는 위와 같이 9, 9를 탐색하는 경우이다. 이후에는 조건에 따라 y + 1된 10값이 될 것이고 x는 그대로 9가 된다(코드 참고). 그러므로 x는 9, y는 10일때가 재귀함수의 종료 조건 부분이 되고 이때 min값을 계산해 주면 된다.

 

풀고보니 정말 간단한 구현인데,,, 풀때는 정말 어려웠다.

코드

import java.util.*;
 
public class Main {    
    
    static int[][] board;
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        board = new int[10][10];
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < 10; j++) {
                board[i][j] = scan.nextInt();
            }
        }
        
        int[] remain = {0, 5, 5, 5, 5, 5}; //각 색종이의 남은 개수를 표현한다.
        bp(0, 0, remain, 0); //0,0부터 오른쪽 아래로 이동하며 색종이를 덮어 나간다.
        
        if(min == Integer.MAX_VALUE) System.out.println("-1");
        else System.out.println(min);
    }    
    
    public static void bp(int x, int y, int[] remain, int count) {
        if(x == 9 && y == 10) { //마지막에 도달했을때
            min = Math.min(min, count);
            return;
        }
        if(y == 10) { //오른쪽으로 이동하다가 범위를 벗어나면 아래로 이동
            bp(x + 1, 0, remain, count);
            return;
        }
        if(count >= min) return; //현재 count가 최소값보다 크다면 더 이상 계산할 필요가 없다.
        
        if(board[x][y] == 1) {
            for(int j = 5; j >= 1; j--) {//제일 큰 색종이 사이즈 부터 붙일 수 있는지 확인한다.
                if(isAttach(x, y, j) && remain[j] > 0) { //색종이를 더 붙일 수 있다면 붙인다.
                    attach(x, y, j); //현재 위치에 j크기의 색종이를 붙여준다.
                    remain[j]--; //해당 색종이를 하나 사용하였으므로 감소시켜준다.
                    bp(x, y + 1, remain, count + 1); 
                    detach(x, y, j); //붙였던 색종이를 다시 떼어준다.
                    remain[j]++; //해당 색종이를 다시 떼어냈으므로 증가시켜준다.
                }
            }
        } else { //board[x][y]가 0인경우에는 오른쪽으로
            bp(x, y + 1, remain, count);
        }
    }
    
    //x, y위치에서 부터 size만큼의 색종이를 붙이는 과정.
    public static void attach(int x, int y, int size) {
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                board[i][j] = 2; //색종이 붙였음을 표시
            }
        }
    }
    
    //x, y위치에서 부터 size만큼의 색종이를 떼는 과정.
    public static void detach(int x, int y, int size) {
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                board[i][j] = 1; 
            }
        }
    }
    
    //x, y위치로 부터 size만큼의 색종이를 붙일 수 있는지 확인하는 과정.
    public static boolean isAttach(int x, int y, int size) {
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                if(i >= 10 || j >= 10) return false;
                if(board[i][j] != 1) return false; 
            }
        }
        return true;
    }
}