[백준] 17136: 색종이 붙이기 (Java, Python)

색종이 붙이기

백준 17136 백트래킹 브루트포스 그리디 Python Java

문제 분석

• 10×10 격자에 0과 1이 있음
• 1×1 ~ 5×5 색종이 각 5개씩 보유
• 모든 1을 색종이로 덮되, 겹침/0 덮기/경계 초과 불가
• 최소 색종이 개수를 구하거나, 불가능하면 -1 출력

접근법

• 백트래킹: 좌상단부터 스캔하여 처음 만나는 1에 색종이 배치 시도
• 큰 것부터 (5×5 → 1×1): 큰 색종이가 적은 개수로 많이 덮으므로
• Pruning: 현재 사용량 ≥ 최적해이면 즉시 컷

핵심 아이디어

• 좌상단부터 스캔하면, 처음 발견한 1은 반드시 그 위치가 좌상단이 되는 색종이로 덮어야 함
• 그래야 빠짐없이 모든 칸을 커버할 수 있음
• 해당 칸에 k×k (5~1) 색종이를 놓고 → 재귀 → 백트래킹
• 어떤 크기도 안 되면 현재 분기는 실패 → return

풀이 (Python)

import sys
input = sys.stdin.readline

grid = [list(map(int, input().split())) for _ in range(10)]
cnt = [0] * 6   # cnt[k]: k×k 색종이 사용 개수
ans = float('inf')

def can_place(r, c, k):
    """(r,c)에 k×k 색종이를 놓을 수 있는지"""
    if r + k > 10 or c + k > 10:
        return False
    for i in range(r, r + k):
        for j in range(c, c + k):
            if grid[i][j] != 1:
                return False
    return True

def fill(r, c, k, val):
    """k×k 영역을 val로 채우기"""
    for i in range(r, r + k):
        for j in range(c, c + k):
            grid[i][j] = val

def solve(used):
    global ans
    if used >= ans:       # pruning
        return
    # 좌상단부터 첫 번째 1 찾기
    for i in range(10):
        for j in range(10):
            if grid[i][j] == 1:
                # 이 칸에 k×k 색종이 시도 (큰 것부터)
                for k in range(5, 0, -1):
                    if cnt[k] < 5 and can_place(i, j, k):
                        fill(i, j, k, 0)
                        cnt[k] += 1
                        solve(used + 1)
                        cnt[k] -= 1
                        fill(i, j, k, 1)   # 백트래킹
                return   # 이 칸을 반드시 덮어야 하므로 return
    # 모든 칸이 0 → 완성
    ans = used

solve(0)
print(ans if ans != float('inf') else -1)

풀이 (Java)

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

public class Main {
    static int[][] g = new int[10][10];
    static int[] cnt = new int[6];
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++)
                g[i][j] = Integer.parseInt(st.nextToken());
        }
        solve(0);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }

    static boolean canPlace(int r, int c, int k) {
        if (r + k > 10 || c + k > 10) return false;
        for (int i = r; i < r + k; i++)
            for (int j = c; j < c + k; j++)
                if (g[i][j] != 1) return false;
        return true;
    }

    static void fill(int r, int c, int k, int v) {
        for (int i = r; i < r + k; i++)
            for (int j = c; j < c + k; j++)
                g[i][j] = v;
    }

    static void solve(int used) {
        if (used >= ans) return;
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                if (g[i][j] == 1) {
                    for (int k = 5; k >= 1; k--) {
                        if (cnt[k] < 5 && canPlace(i, j, k)) {
                            fill(i, j, k, 0);
                            cnt[k]++;
                            solve(used + 1);
                            cnt[k]--;
                            fill(i, j, k, 1);
                        }
                    }
                    return;
                }
        ans = used;
    }
}

예제 트레이스

예제 6: 10×10 전부 1

첫 번째 1 = (0,0)
  5×5 배치 → (0,0)~(4,4) 덮음, used=1

  다음 첫 1 = (0,5)
    5×5 배치 → (0,5)~(4,9) 덮음, used=2

    다음 첫 1 = (5,0)
      5×5 배치 → (5,0)~(9,4) 덮음, used=3

      다음 첫 1 = (5,5)
        5×5 배치 → (5,5)~(9,9) 덮음, used=4

        모든 칸 0 → ans = 4 ✓

---

예제 4: L자 모양들
  (1,1)(1,2)(2,2) = L자 → 1×1로만 가능 (3장)
  (3,4)(3,5)(4,5) = L자 → 1×1로만 가능 (3장)
  (6,2) = 1×1 (1장)
  총 7장 필요하지만 1×1은 5장까지 → 불가능 (-1) ✓

시간 복잡도

O(5^K)

K = 1의 개수, pruning으로 실제 매우 빠름

공간 복잡도

O(100)

10×10 격자 + 재귀 스택

클린 코드 — Python

import sys
input = sys.stdin.readline
grid = [list(map(int, input().split())) for _ in range(10)]
cnt = [0]*6; ans = float('inf')
def can(r,c,k):
    if r+k>10 or c+k>10: return False
    return all(grid[i][j]==1 for i in range(r,r+k) for j in range(c,c+k))
def fill(r,c,k,v):
    for i in range(r,r+k):
        for j in range(c,c+k): grid[i][j]=v
def solve(used):
    global ans
    if used>=ans: return
    for i in range(10):
        for j in range(10):
            if grid[i][j]==1:
                for k in range(5,0,-1):
                    if cnt[k]<5 and can(i,j,k):
                        fill(i,j,k,0); cnt[k]+=1
                        solve(used+1)
                        cnt[k]-=1; fill(i,j,k,1)
                return
    ans=used
solve(0)
print(ans if ans!=float('inf') else -1)

클린 코드 — Java

import java.io.*;
import java.util.*;
public class Main {
    static int[][] g=new int[10][10]; static int[] c=new int[6]; static int ans=Integer.MAX_VALUE;
    public static void main(String[] a) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        for(int i=0;i<10;i++){StringTokenizer st=new StringTokenizer(br.readLine());for(int j=0;j<10;j++)g[i][j]=Integer.parseInt(st.nextToken());}
        solve(0); System.out.println(ans==Integer.MAX_VALUE?-1:ans);
    }
    static boolean can(int r,int cl,int k){if(r+k>10||cl+k>10)return false;for(int i=r;i<r+k;i++)for(int j=cl;j<cl+k;j++)if(g[i][j]!=1)return false;return true;}
    static void fill(int r,int cl,int k,int v){for(int i=r;i<r+k;i++)for(int j=cl;j<cl+k;j++)g[i][j]=v;}
    static void solve(int u){
        if(u>=ans)return;
        for(int i=0;i<10;i++)for(int j=0;j<10;j++)if(g[i][j]==1){
            for(int k=5;k>=1;k--)if(c[k]<5&&can(i,j,k)){fill(i,j,k,0);c[k]++;solve(u+1);c[k]--;fill(i,j,k,1);}return;}
        ans=u;
    }
}