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

[백준] 17136. 색종이 붙이기

 

📌 풀이 과정

큰 색종이를 먼저 붙이는 것이 효율적이므로

큰 색종이로 덮을 수 있는 범위를 줄이고, 남은 작은 영역에 더 작은 색종이를 붙이도록 해야한다.

그리고 색종이를 붙이는 과정에서 잘못된 선택일 경우, 다시 돌아와서 더 작은 색종이를 붙이는 로직이 필요하다.

즉, 색종이를 붙이는 순서에 따라 최종 결과가 달라지기 때문에 모든 경우를 시도하는 백트래킹이 필요하다.

 

1️⃣ DFS 탐색

• (x, y) 좌표에서 색종이를 붙이면서 최소한의 색종이를 찾기 위해 재귀적으로 탐색한다.
• 기저 조건: x >= 10에 도달하면 모든 칸을 탐색한 것이므로, 사용한 색종이 개수(usedPapers)를 최솟값으로 갱신한다.
• (y >= 10)일 때는 한 행을 다 탐색한 것이므로 다음 행으로 이동한다.

2️⃣ 색종이 붙이는 과정

• paper[x][y] == 1일 때는 색종이를 붙일 수 있는 위치입니다.
• canPlacePaper() 함수는 (x, y)에서 크기가 size인 색종이를 붙일 수 있는지 확인한다.
  • 이때, 경계를 벗어나지 않는지, 색종이를 붙일 모든 칸이 1인지 확인한다.
• 색종이를 붙일 수 있으면, placePaper() 함수를 통해 색종이를 붙이거나 떼는 작업을 수행한다.

3️⃣ 색종이 사용 관리

• type[] 배열을 사용해 각 크기의 색종이를 최대 5개까지만 사용할 수 있도록 제한한다.

 

✨ 제출 코드

메모리 : 22616 KB
시간 : 200 ms

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


public class 색종이붙이기_17136 {

    static int answer = Integer.MAX_VALUE;
    static int[] type = {0, 5, 5, 5, 5, 5}; // 각 크기별 색종이 사용 가능 개수
    static int[][] paper = new int[10][10];

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

        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, 0, 0);

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

    private static void dfs(int x, int y, int usedPapers) {
        if (usedPapers >= answer) return;

        // 종이를 전부 다 덮은 경우
        if (x >= 10) {
            answer = Math.min(answer, usedPapers);
            return;
        }

        // 다음 행으로 이동
        if (y >= 10) {
            dfs(x + 1, 0, usedPapers);
            return;
        }

        // 이미 덮인 곳이면 다음 칸으로 이동
        if (paper[x][y] == 0) {
            dfs(x, y + 1, usedPapers);
            return;
        }

        // 1을 덮을 수 있는 색종이를 큰 것부터 시도
        for (int size = 5; size >= 1; size--) {
            if (canPlacePaper(x, y, size)) {
                placePaper(x, y, size, 0); // 색종이 붙이기
                type[size]--;

                dfs(x, y + 1, usedPapers + 1); // 다음 칸으로

                placePaper(x, y, size, 1); // 색종이 제거
                type[size]++;
            }
        }
    }

    // 해당 위치에 size 크기의 색종이를 붙일 수 있는지 확인
    private static boolean canPlacePaper(int x, int y, int size) {
        if (type[size] == 0) return false; // 해당 크기의 색종이를 더 이상 사용할 수 없는 경우

        if (x + size > 10 || y + size > 10) return false;

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (paper[x + i][y + j] == 0) return false;
            }
        }

        return true;
    }

    // 색종이를 붙이거나 떼는 함수 (flag가 0이면 붙이고, 1이면 떼는 역할)
    private static void placePaper(int x, int y, int size, int flag) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                paper[x + i][y + j] = flag;
            }
        }
    }
}