백준 17136 - 색종이 붙이기

문제

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

풀이

• 문제를 처음 접했을 때 탐색의 범위가 $10 \times 10$으로 매우 작으므로, 완전탐색으로 풀이가 가능할 것으로 생각했다.
• 최소 개수의 색종이로 1인 범위를 커버하는 것이 관건이므로, 큰 색종이부터 붙이는 방식으로 접근하였다.
• 관건은 무조건 큰 색종이부터 붙이는 형태가 답이 아닐 수 있기 때문에 모든 경우의 수를 고려할 수 있도록 색종이를 붙였다 떼기를 반복해야 한다는 점이다.
• 따라서, 백트래킹을 통해 색종이를 붙였다 떼며 모든 경우에 따라 최소 개수를 갱신하는 방식으로 로직을 구현하였다.

로직의 시간복잡도는 정확히 가늠하기 어려우나 $10 \times 10$의 배열 내에서 색종이를 붙이는 모든 경우의 수를 다 구하므로 사실상 상수 시간에 가깝다. 따라서 제한 조건 1초를 무난히 통과한다.

코드

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

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

public class Main {

  static int[][] matrix = new int[10][10];
  static int[] papers = {0, 5, 5, 5, 5, 5};
  static int ans = MAX_VALUE;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    for (int r = 0; r < 10; r++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int c = 0; c < 10; c++) {
        matrix[r][c] = parseInt(st.nextToken());
      }
    }

    dfs(0, 0, 0);
    System.out.println(ans == MAX_VALUE ? -1 : ans);
    br.close();
  }

  static boolean canAttach(int r, int c, int size) {
    for (int row = r; row < r + size; row++) {
      for (int col = c; col < c + size; col++) {
        if (row < 0 || row >= 10 || col < 0 || col >= 10) {
          return false;
        }

        if (matrix[row][col] != 1) {
          return false;
        }
      }
    }

    return true;
  }

  static void attach(int r, int c, int size, int value) {
    for (int row = r; row < r + size; row++) {
      for (int col = c; col < c + size; col++) {
        matrix[row][col] = value;
      }
    }
  }

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

    if (ans <= count) {
      return;
    }

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

    if (matrix[r][c] == 1) {
      for (int size = 5; size >= 1; size--) {
        if (papers[size] == 0 || !canAttach(r, c, size)) {
          continue;
        }

        attach(r, c, size, size);
        papers[size]--;
        dfs(r, c + 1, count + 1);
        attach(r, c, size, 1);
        papers[size]++;
      }
    } else {
      dfs(r, c + 1, count);
    }
  }
}

결과