[백준 - 17136번] 색종이 붙이기 - Java

문제 링크

https://www.acmicpc.net/problem/17136

문제

티어: 골드 2
알고리즘: 브루트포스, 백트래킹
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

풀이

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력해야 한다.

이 문제는 브루트포스, 백트래킹으로 풀 수 있다.

주어진 입력인 10x10을 [0][0] ~ [9][9]까지 탐색해 본다.

만약 값이 1이라면 색종이를 붙여야하기 때문에 5가지 색종이 중 하나를 붙이면 된다.

당연히 색종이를 붙이기 전에 붙일 수 있는지를 체크해 줘야 한다.

색종이를 붙일 때는 현재 1이 색종이의 왼쪽 위 꼭짓점이라고 생각하고 붙이면 된다.

그러면 색종이 종류 별 범위를 쉽게 구할 수 있고, 그 범위가 전부 1이라면 색종이를 붙일 수 있다.

이렇게 붙여나갔을 때 모든 1를 가릴 수 없다면, answer은 초깃값을 가지게 될 것이다.

만약 모든 1를 가릴 수 있다면, y = 10을 가리킬 것이고, 이때 cnt값은 answer보다 작은 값이 된다.

일단 종료 조건이 y = 10인 이유는 nx, ny를 구할 때 nx = x + 1; ny = y이고,

nx가 10이 되면 nx = 0, ny += 1를 해준다. 그러면 ny = 9이고, nx = 9이고, 다음을 넘어간다면, ny가 10이 됨을 의미한다.

y가 10일 때 cnt값이 answer보다 작은 이유는 cnt >= answer인 경우는 더 깊이 들어가지 못하게 back해줬기 때문이다.

이 방식대로 풀면 답을 구할 수 있다.

자세한 구현 사항은 코드를 보길 바란다.

소스 코드

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

public class Main {
    static int[] cp = {5, 5, 5, 5, 5}; //0부터 1, 2, 3...
    static int answer = 30;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int[][] map = new int[10][10];
      for(int i=0; i<10; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for(int j=0; j<10; j++) {
              map[i][j] = Integer.parseInt(st.nextToken());
          }
      }
      
      dfs(map, 0, 0, 0);
      if(answer == 30) {
          System.out.println(-1);
      } else {
          System.out.println(answer);
      }
  }
  
  static void dfs(int[][] map, int x, int y, int cnt) {
      if(cnt >= answer) {
          return;
      }
      
      if(y == 10) {
          answer = cnt;
          return;
      }
      
      int nx = x + 1;
      int ny = y;
      if(nx == 10) {
          nx = 0;
          ny += 1;
      }
      
      if(map[y][x] == 0) {
          dfs(map, nx, ny, cnt);
      } else {
          for(int i=0; i<5; i++) {
              if(cp[i] >= 1 && check(map, x, y, i + 1)) {
                  //색종이 붙이기가 가능하다면 영역이 전부 1임을 뜻함.
                  paste(map, x, y, i + 1);
                  cp[i] -= 1;
                  dfs(map, nx, ny, cnt + 1);
                  cp[i] += 1;
                  takeOff(map, x, y, i + 1);
              }
          }
      }
  }
  
  static boolean check(int[][] map, int x, int y, int type) {
      int maxY = y + type - 1;
      int maxX = x + type - 1;
      if(maxY >= 10 || maxX >= 10) {
          return false;
      }
      for(int i=y; i<=maxY; i++) {
          for(int j=x; j<=maxX; j++) {
              if(map[i][j] == 0) {
                  return false;
              }
          }
      }
      return true;
  }
  
  static void paste(int[][] map, int x, int y, int type) {
      int maxY = y + type - 1;
      int maxX = x + type - 1;
      
      for(int i=y; i<=maxY; i++) {
          for(int j=x; j<=maxX; j++) {
              map[i][j] = 0;
          }
      }
  }
  
  static void takeOff(int[][] map, int x, int y, int type) {
      int maxY = y + type - 1;
      int maxX = x + type - 1;
      
      for(int i=y; i<=maxY; i++) {
          for(int j=x; j<=maxX; j++) {
              map[i][j] = 1;
          }
      }
  }
}