백준 17136 색종이 붙이기

A형 기출문제라고 한다.

처음에 큰 거 부터 넣어서 그리디로 풀려고 했는데, 모양에 따라 답이 틀려지는 것을 알게 되어서 완탐으로 풀었다.

 

색종이를 붙여야 하는 공간을 10*10으로 매번 찾기보다는 해당 (row,col)을 list로 가져오는 것이 더 시간상 빠를 것이라 생각했다.

그리고 완탐을 하려면 1x1의 색종이를 붙이고 모든 경우를 다 해 본후, 다시 돌아와서 2x2의 색종이를 붙이는 방식으로 붙여야 했기 때문에, dfs를 통해 풀었다.

또한, 색종이를 붙이고 난 후에는 해당 공간을 체크해야 하는데, 색종이를 붙일 공간을 2차원 배열로 가지고 있지 않고, list로 가지고 있기 때문에, check(색종이를 붙인 좌표를 체크)라는 1차원 배열만 다음 dfs로 넘겨주어도 되었다.

 

square 함수를 보면, 현재 위치에서 NxN 색종이를 붙일 수 있는지 체크한 후, 해당 위치에 색종이를 붙일 수 있을 경우 check를 해야 했는데(색종이를 붙이는 과정), 이 때 num이라는 2차원 배열에 list 내 해당 좌표의 index를 저장해서 쉽게 찾을 수 있도록 했다.

 

처음에는 시간 초과가 났었다. 이는 list에 색종이를 붙일 수 있는 공간을 찾은 후, 해당 공간에 NxN색종이를 넣어야 했는데(1차원 for문 2개: 다음 위치 for문 + NxN 중 하나 선택 for문), 2중 for문을 돌려서 같은 작업을 여러번 반복했다.

 

마지막으로, dfs의 인자로 계속해서 색종이를 붙일 수 있는 여유 공간을 넘겨 주어서 0이 되면 ans를 계산해 주었고, dfs 진행 중 현재 ans보다 값이 커질 경우 return시켰다.

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static int ans;
    static ArrayList<int[]> list;
    static int[][] map;
    static int[][] num;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
        map = new int[10][10];
        num = new int[10][10];
        int cnt = 0;
        list = new ArrayList<int[]>();
        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());
                if (map[i][j] == 1) {
                    num[i][j] = cnt++;
                    int[] temp = { i, j };
                    list.add(temp);
                }
            }
        }
 
        ans = Integer.MAX_VALUE;
        cnt = list.size();
        boolean[] check = new boolean[cnt];
        int[] squares = { 5, 5, 5, 5, 5 };
        dfs(cnt, squares, check);
 
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
 
    private static void dfs(int cnt, int[] squares, boolean[] check) {
        int sum = 0;
        for (int i = 0; i < 5; i++)
            sum += squares[i];
        if (25 - sum > ans)// 이미 ans 보다 많이 썼으면 return
            return;
        if (cnt == 0) {// 모든 곳을 다 덮었으면
            if (25 - sum < ans) {// 총 사용 횟수가 ans보다 작으면
                ans = 25 - sum;
            }
            return;
        }
        if (sum == 0)// 모든 종이를 다썼으면 return
            return;
 
        int next = -1;
        for (int i = 0; i < list.size(); i++) {
            if (!check[i]) {// 아직 덮지 않은 곳이면
                next = i;
                break;
            }
        }
 
        if (next == -1)
            return;
        for (int j = 4; j >= 0; j--) {// 한 변의 길이가 얼마일 때까지 덮을 수 있는가 체크
            if (squares[j] == 0)
                continue;
            boolean[] cp_check = new boolean[list.size()];
            cp_check = check.clone();
            if (square(next, j, cp_check)) {
                int[] cp_squares = new int[5];
                cp_squares = squares.clone();
                cp_squares[j]--;
 
                dfs(cnt - (j + 1) * (j + 1), cp_squares, cp_check);
            } else
                continue;
        }
 
    }
 
    private static boolean square(int idx, int length, boolean[] check) {
        int row = list.get(idx)[0];
        int col = list.get(idx)[1];
        for (int i = row; i <= row + length; i++) {
            if (i >= 10)
                return false;
            for (int j = col; j <= col + length; j++) {
                if (j >= 10)
                    return false;
                if (check[num[i][j]] || map[i][j] == 0) {// 정사각형으로 찾는데, 못만들면 false return, 만들 수 있으면 true return
                    return false;
                }
            }
        }
        for (int i = row; i <= row + length; i++) {
            for (int j = col; j <= col + length; j++) {
                check[num[i][j]] = true;
            }
        }
        return true;
    }
}