[BOJ/Java] 17136. 색종이 붙이기

[BOJ/Java] 17136. 색종이 붙이기

17136번: 색종이 붙이기

---

문제 해석

본 문제는 10x10 크기의 그리드에서 1로 표시된 부분을 최소 개수의 색종이로 모두 덮는 최적의 방법을 찾는 것이다. 사용 가능한 색종이의 크기는 1x1부터 5x5까지 다양하며, 각 크기의 색종이는 최대 5개까지 사용할 수 있다. 문제의 핵심은 최소한의 색종이 사용으로 모든 1을 덮는 것이다.

풀이 과정

1. 초기화 및 입력 처리: 그리드를 10x10 크기의 배열로 초기화하고, 입력을 받아 해당 배열을 채운다.
2. 재귀적 탐색: 재귀 함수 recursive를 사용하여 가능한 모든 색종이 위치를 시도한다. x와 y는 그리드의 위치를 나타내며, c는 현재까지 사용된 색종이의 수다.
3. 색종이 배치 가능성 검사: getPaperSize 함수를 통해 주어진 위치에 배치할 수 있는 최대 크기의 색종이를 찾는다. 이 크기는 색종이가 그리드 경계를 벗어나지 않고, 이미 색종이가 붙어 있는 곳을 덮지 않는 범위에서 결정된다.
4. 색종이 배치: 가능한 색종이 크기를 찾으면 해당 크기의 색종이를 붙이고, 재귀적으로 다음 위치를 탐색한다. 탐색 후에는 색종이를 제거하여 다른 가능성을 탐색한다.

코드

package edu.ssafy.im.BOJ.Gold.G2.No17136;

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int N = 10; // 그리드의 크기
    private static int ans = Integer.MAX_VALUE; // 최소 색종이 개수, 최대값으로 초기화
    private static int[][] map; // 그리드를 나타내는 배열
    private static int SIZE = 5; // 최대 색종이 크기
    private static int[] papers = {0, 5, 5, 5, 5, 5}; // 사용 가능한 각 크기의 색종이 개수

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

        map = new int[N][N]; // 그리드 초기화
        for (int x = 0; x < N; x++) {
            st = new StringTokenizer(br.readLine());
            for (int y = 0; y < N; y++) {
                map[x][y] = Integer.parseInt(st.nextToken()); // 그리드에 값 입력
            }
        }

        recursive(0, 0, 0); // 재귀적 탐색 시작

        sb.append(ans == Integer.MAX_VALUE ? -1 : ans); // 결과 출력

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void recursive(int x, int y, int c) {
        if (x == 10) { // 모든 행을 다 탐색했을 경우
            ans = Math.min(ans, c); // 최소 색종이 개수 갱신
            return;
        }

        if (map[x][y] == 0) { // 현재 위치에 색종이 필요 없는 경우
            if (y == 9) recursive(x + 1, 0, c); // 다음 행으로 이동
            else recursive(x, y + 1, c); // 같은 행의 다음 열로 이동
        } else if (map[x][y] == 1) { // 현재 위치에 색종이 필요한 경우
            int size = getPaperSize(x, y); // 가능한 색종이 크기를 얻는다
            if (size == -1) return; // 색종이를 붙일 수 없는 경우, 종료

            for (int i = 1; i <= size; i++) {
                if (papers[i] > 0) {
                    for (int nx = 0; nx < i; nx++) {
                        for (int ny = 0; ny < i; ny++) {
                            map[x + nx][y + ny] = 0; // 색종이 붙이기
                        }
                    }

                    papers[i]--; // 사용한 색종이 개수 감소

                    if (y + i >= 10) recursive(x + 1, 0, c + 1); // 색종이를 붙이고 다음 위치로 이동
                    else recursive(x, y + i, c + 1);

                    for (int nx = 0; nx < i; nx++) {
                        for (int ny = 0; ny < i; ny++) {
                            map[x + nx][y + ny] = 1; // 색종이 제거
                        }
                    }

                    papers[i]++; // 사용했던 색종이 복원
                }
            }
        }
    }

    private static int getPaperSize(int nx, int ny) {
        for (int size = SIZE; size > 0; size--) { // 최대 크기에서부터 시작하여 가능한 색종이 크기를 찾는다
            boolean flag = true;
            L:
            for (int x = nx; x < nx + size; x++) {
                for (int y = ny; y < ny + size; y++) {
                    if (x < 0 || y < 0 || x >= N || y >= N || map[x][y] == 0) {
                        flag = false;
                        break L;
                    }
                }
            }
            if (flag) return size; // 적합한 크기를 찾은 경우
        }
        return -1; // 적합한 크기를 찾지 못한 경우
    }
}

시간 복잡도 분석

본 알고리즘의 시간 복잡도는 색종이를 붙이는 모든 경우의 수를 탐색하기 때문에 최악의 경우 매우 높다. 각 위치에서 최대 5x5 크기의 색종이를 붙일 수 있으며, 이러한 경우의 수가 겹치는 경우가 많다. 재귀적으로 모든 가능성을 탐색하므로 시간 복잡도는 지수적으로 증가할 수 있다.

느낀점

이 문제를 통해 완전 탐색과 백트래킹의 중요성을 다시 한 번 깨달았다. 최적의 해를 찾기 위해서는 모든 가능성을 고려해야 하며, 효율적인 백트래킹을 통해 불필요한 계산을 줄일 필요가 있다는 것을 배웠다. 또한, 문제의 조건을 세심하게 분석하고 이를 코드에 반영하는 능력이 중요함을 느꼈다.