백준 - 색종이 붙이기(17136)

오늘 풀어본 문제는 ⭐색종이 붙이기 라는 문제이다.

1. 문제요약

• 1×1, 2×2, 3×3, 4×4, 5×5 색종이가 총 5개씩 있다.
• 10×10 색종이를 위 5종류의 색종이로 채워야한다.
  • 각 칸에는 0,1이 적혀있다.
  • 1에는 색종이로 가려야 하고, 0은 가려선 안된다.
• 겹치면 안된다.

2. 입출력

출력

불가능한 경우 -1 출력

3. 알고리즘

• 핵심 상태
  • paper[][] : 현재 남아있는 1 영역
  • remain [] : 색종이 남은 개수
  • answer : 최소 사용 개수
• 진행 방식
  • dfs 함수 내에서, 이중 for문으로 행,열 처음부터 보며 1 찾음
    • 1 찾으면 즉시 중단 및 1 찾았다는 boolean 변수 true로 변경
  • 1 찾은 위치에 대해 5×5 ~ 1×1 색종이를 모두 시도
    • 붙일 수 있다면 다음 재귀로 이동(인자는 현재까지 계산된 색종이의 총 합)
• 핵심 규칙
  • 붙일 때 해당 영역 0으로 변경
  • 재귀 후 다시 1로 복귀
  • 색종이 개수도 다시 복구
  • used >= answer 면 가지치기로 재귀 탐색 x
• 이동 처리
  • 매 DFS마다 왼쪽 위부터 첫 번째 1 탐색
  • (r,c)에서 size×size 범위 검사
• 종료 조건
  • 더 이상 1이 없으면 정답 갱신
• 시간복잡도
  • 완전탐색 + 백트래킹
  • 가지치기로 줄임

4. 코드

public class Main {
    static int[][] PAPER;
    static int[] TYPE_CNT = {0, 5, 5, 5, 5, 5};
    static int ANSWER;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PAPER = new int[10][10];
        ANSWER = Integer.MAX_VALUE;

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

        dfs(0);

        System.out.println(ANSWER == Integer.MAX_VALUE ? -1 : ANSWER);
    }

    static void dfs(int used) {
        if (used >= ANSWER) {
            return;
        }

        boolean found = false;
        int r = 0;
        int c = 0;
        for (r = 0; r < 10; r++) {
            for (c = 0; c < 10; c++) {
                if (PAPER[r][c] == 1) {
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }

        if (!found) {
            ANSWER = Math.min(ANSWER, used);
            return;
        }

        for (int size = 1; size <= 5; size++) {
            if (!canGo(r,c,size))
                continue;
            attach(r, c, size, 0);
            TYPE_CNT[size]--;
            dfs(used + 1);
            attach(r, c, size, 1);
            TYPE_CNT[size]++;
        }
    }

    static boolean canGo(int r, int c, int size) {
        if (r + size > 10 || c + size > 10 || TYPE_CNT[size] == 0) {
            return false;
        }

        for (int nr = r; nr < r + size; nr++) {
            for (int nc = c; nc < c + size; nc++) {
                if (PAPER[nr][nc] == 0) {
                    return false;
                }
            }
        }

        return true;
    }

    static void attach(int r, int c, int size, int value) {
        for (int nr = r; nr < r + size; nr++) {
            for (int nc = c; nc < c + size; nc++) {
                PAPER[nr][nc] = value;
            }
        }
    }
}