[BOJ] 17136번 색종이 붙이기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static final int N = 10;
    static int min = Integer.MAX_VALUE;
    static int[][] paper = new int[N][N];
    static int[] sizes = {0, 5, 5, 5, 5, 5};

    public static void main(String[] args) throws IOException {
        init();
        dfs(0, 0, 0);
        print();
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    private static void dfs(int r, int c, int cnt) {
        // 가지치기
        if (cnt >= min) return;
        // 모든 행을 다 확인한 경우 최솟값 갱신
        if (r >= N) {
            // 최솟값 갱신
            min = cnt;
            return;
        }
        // 다음 행으로 이동
        if (c >= N) {
            dfs(r + 1, 0, cnt);
            return;
        }
        // 색종이를 놓을 수 있는지 확인 (큰 색종이부터 확인)
        if (paper[r][c] == 1) {
            for (int i = 5; i >= 1; i--) {
                if (sizes[i] > 0 && check(r, c, i)) {
                    set(r, c, i, 0);
                    sizes[i]--;
                    dfs(r, c + 1, cnt + 1);
                    set(r, c, i, 1);
                    sizes[i]++;
                }
            }
        } else {
            dfs(r, c + 1, cnt);
        }
    }

    private static boolean check(int r, int c, int size) {
        int nr = r + size;
        int nc = c + size;
        if (nr > N || nc > N) return false;
        for (int i = r; i < nr; i++) {
            for (int j = c; j < nc; j++) {
                if (paper[i][j] != 1) return false;
            }
        }
        return true;
    }

    private static void set(int r, int c, int size, int val) {
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                paper[i][j] = val;
            }
        }
    }

    private static void print() {
        if (min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(min);
    }
}

📄 해설

• 백트래킹, DFS 로 해결하였음

• 2차원 배열에 대한 DFS 이므로, 행번호 r, 열번호 c, 현재까지 붙인 색종이 개수 cnt 를 매개변수로 계속 전달하여, 재귀 수행을 함

• 우선, 기저조건은 마지막 행에 도착했을 때이며, 이때 최솟값을 갱신함

  • Math.min 으로 하지 않은 이유?
    if(cnt >= min) 을 통해 가지치기 를 하고 있기 때문
    어차피 최솟값이 한번 정해지면, 그보다 작은 값이 아닌 이상, 마지막 행에 도달할 수 없음

• 색종이를 놓을 수 있는 경우는 해당 칸이 1 인 경우이며, 0 인 경우 바로 다음 열을 확인

• 1 인 경우 두가지를 확인해야함

  1. 1x1 ~ 5x5 의 색종이의 남은 개수를 확인해야함 -> sizes[i] > 0
     • 이때, 5x5 크기의 색종이부터 확인을 해야함
     • 최솟값이 되기 위해서는 한번에 많은 영역을 덮어야하기 때문에 큰 것부터 확인을 해야함.
     • 일종의 그리디 접근이라고 볼 수 있겠음
  2. 해당 위치를 시작점으로 하여 다른 칸들에 색종이를 놓을 수 있는 지를 확인해야함 -> check 메소드
  • 1 과 2 에 해당하는 경우, 해당 위치를 색종이로 덮고, 다음 칸으로 이동 (set 메소드, size[i]--)
    값을 변경시켜 주었으므로, 재귀를 나올때 꼭 값 복귀를 시켜주어야함!

• 지금까지 기술한 일련의 과정을 다 수행하면 됨

실수했던 부분

check 메소드에서 범위체크를 하는 부분.
어이없게도 nr 과 nc 는 N 이어도 상관없는데, N 이면 안되게 설정을 해버렸었음
역시 범위체크는 휴먼 에러가 대부분.