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

BOJ Link

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

 

개요

처음에 depth가 엄청 깊어질 거라 생각해서 그리디하게 풀 수 있나 생각했다. 반례로 안된다고 확정지었다.

완탐으로 구현했는데, 역시나  1의 개수가 많아질수록 복잡도가 팩토리얼 단위로 늘어나므로 IDE에서도 오래걸렸다.

(정확한 시간 복잡도 계산은 까다로웠다.)

풀이 과정

이중 for문을 사용해 탐색하며 3가지 최적화를 했다. (그럼에도 통과하지 못했다.)

 

1. 매 dfs 탐색 마다 map이 전부 0인지 세기 -> 붙이기/떼기 동작에서 같이 세기

map이 10*10이라 그냥 매 탐색마다 셌었는데 바꿨다.

 

2. size 1 to 5탐색 -> size 5 to 1로 바꾸기

가지치기에 현재 cnt가 ans 이상이면 return하는 조건이 있다.

size가 더 큰 종이 우선으로 채웠을 때,  정답 후보라면 ans가 더 적어진다. 이 경우에 전체 탐색 횟수를 줄일 수 있다.

 

3. 배열 탐색마다 깊은 복사하기 -> 갱신 후 넘기고 형상복귀하기

메모리 걱정도 배제할 수 있고, 성능도 늘어날 것이라 생각했다.

 

이후 정답 코드를 찾아보니 idx(i,j)를 옮기는 방법이 있었다.

for문과 유사한 순차탐색 동작을 하지만, 탐색 범위가 줄어들어 통과할 수 있었다.

 

제출 코드

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

class Main {
    static int ans = 26;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[][] map = new int[10][10];

        for (int i = 0; i < 10; i++)
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // size 1~5별 남은 종이 개수
        int[] paper = new int[5];
        Arrays.fill(paper, 5);

        // 붙여야 하는 종이 수
        int remain = 0;
        for (int[] row : map) remain += (int) Arrays.stream(row).filter(v -> v == 1).count();

        dfs(0, 0, map, 0, remain, paper);

        System.out.println(ans == 26 ? -1 : ans);
    }

    public static void dfs(int i, int j, int map[][], int cnt, int remain, int[] paper) {

        // 종료 조건 1 & 가치지기 - 현재 해가 최적이 아닐 때
        if (i == 10 || cnt >= ans) return;

        // col 범위 벗어나면 row += 1, col = 0
        if (j == 10) {
            dfs(i + 1, 0, map, cnt, remain, paper);
            return;
        }

        // 종료 조건 2 - 종이 다 채운 경우
        if (remain == 0) {
            ans = Math.min(cnt, ans);
            return;
        }

        // 종이를 붙일 수 있으면 탐색
        if (map[i][j] == 1) {
            // 붙일 종이 사이즈 큰 순서로 탐색 - 가지치기 조건 좀 더 빨리 걸리게
            for (int size = 5; size > 0; size--) {
                // 답의 후보고, 경계안이고, 해당 사이즈의 종이가 남아있으면
                if (cnt < ans && isIn(i, j, map, size) && paper[size - 1] > 0) {

                    // 갱신하고 DFS하고 형상복귀
                    paper[size - 1]--;
                    dfs(i, j, map, cnt + 1, attach(i, j, size, remain, 0, map), paper);
                    attach(i, j, size, remain, 1, map);
                    paper[size - 1]++;
                }
            }
        }
        // 붙일 수 없으면 다음 col 탐색
        else dfs(i, j + 1, map, cnt, remain, paper);

    }

    // flag 1일 때 attach, flag 0일 때 detach
    public static int attach(int sr, int sc, int size, int remain, int flag, int[][] map) {

        for (int i = sr; i < sr + size; i++) {
            for (int j = sc; j < sc + size; j++) {
                map[i][j] = flag;
            }
        }

        // flag 별 남은 종이 개수 갱신
        int multi = flag == 1 ? 1 : -1;
        remain += size * size * multi;

        return remain;
    }

    public static boolean isIn(int r, int c, int[][] map, 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++) {
                if (map[i][j] == 0) return false;
            }
        }

        return true;
    }

//    // 2차원
//    public static int[][] deepClone(int[][] arr) {
//        int[][] newArr = new int[arr.length][];
//        for (int i = 0; i < arr.length; i++) newArr[i] = deepClone(arr[i]);
//        return newArr;
//    }
//
//    // 1차원
//    public static int[] deepClone(int[] arr) {
//        return Arrays.stream(arr).toArray();
//    }

}