[Java/백트래킹] 백준 17136. 색종이 붙이기

17136번: 색종이 붙이기

🤔 Intuition

처음에는 그리디하게 풀 수 있을까 싶었지만, 예외가 있을 것으로 보였다.

그래서 주어진 조건을 보면서 백트래킹을 이용한 완탐으로 풀 수 있을 것으로 봤고, 다행히 추측이 맞았다. (근데 합리적으로 정확하게 계산을 못하겠다... 이 글을 보는 사람은 풀이의 도움을 얻으려는 사람 뿐이겠지만 누군가 백트래킹 시간복잡도 계산에 대하여 잘 안다면 좀 알려주세요....)

🔎 Algorithm & Complexity

* @algorithm backtracking, bruteforce
* @time O(5^100) 는 진~짜 러프하게 잡은 최악, 실제론 가지치기를 통해 많이 줄어든다. -> 516 ms
* @memory O(10*10) -> 37760 KB

 

👨🏻‍💻 Logic

포인트는, 재귀함수 로직 내에서 반복문을 사용하여 좌표들을 순회하려고 하면 로직이 매우 복잡해지므로 파라미터에 탐색하려는 좌표를 담아서 탐색하는 것이다.

 

자, 이제 재귀함수에 좌표를 담아서, 좌표를 이동하면서 각 좌표에 5종류의 색종이를 모두 대보면 답이 나온다.

public class BOJ_17136_색종이붙이기 {
    private static int[][] grid = new int[10][10];
    private static int ans = (int) 1e9;
    private static Map<Integer, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for (int i = 1; i <= 5; i++) {
            map.put(i, 5);
        }

        for (int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        go(0, 0, 0);

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

    private static void go(int y, int x, int depth) {
        if (depth > ans) {
            return;
        }

        if (y == 10 && x == 0) {
            ans = Math.min(ans, depth); // 가능한 최소 개수 반환
            return;
        }

        if (x >= 10) {
            go(y + 1, 0, depth);
            return;
        }

        if (grid[y][x] == 0) {
            go(y, x + 1, depth);
            return;
        }

        for (int l = 5; l >= 1; l--) {
            if (inRange(y, x, l) && canCover(y, x, l) && map.get(l) > 0) {
                apply(y, x, l);
                map.put(l, map.get(l) - 1);

                go(y, x + l, depth + 1);

                remove(y, x, l);
                map.put(l, map.get(l) + 1);
            }
        }
    }

    private static void remove(int y, int x, int l) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                grid[y +i][x + j] = 1;
            }
        }
    }

    private static void apply(int y, int x, int l) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                grid[y +i][x +j] = 0;
            }
        }
    }

    private static boolean canCover(int y, int x, int l) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                if (grid[y + i][x + j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean inRange(int y, int x, int l) {
        return y + l  - 1 < 10 && x + l - 1 < 10;
    }

}