[BOJ] 17136.색종이 붙이기(백트래킹, 시뮬레이션).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

생각보다(?) 간단할 것 같지만

막상 구현하려면 어려운 문제다..

동작은

1. 1이 적힌 칸(색종이를 붙일 수 있는 칸)을 발견!

2. 다섯 종류의 색종이를 모두 붙여볼자!

3. 붙일 수 있다면 붙이고, 1번 동작으로

이렇게 1이 적힌 모든 칸에 스티커가 붙여졌을 때,

색종이의 최소 개수를 구하면 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ17136 {       static int N = 10, oneCnt, map[][];     // 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류, 각 종류의 색종이는 5개씩     static int paperState[] = { 0, 5, 5, 5, 5, 5 };     static int res = 987654321;       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;         map = new int[N][N];           for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             for (int j = 0; j < N; j++) {                 map[i][j] = Integer.parseInt(st.nextToken());                 // 1이 적힌 칸                 if (map[i][j] == 1) oneCnt++;             }         }           go(0, 0);           System.out.println(res == 987654321 ? -1 : res);     }       /**      * 색종이를 붙일 수 있는 칸에 색종이를 붙여보자.      * @param idx    2차원 배열 index      * @param paperCnt    현재까지 사용한 색종이의 수      */     private static void go(int idx, int paperCnt) {         // 색종이를 최소로 사용한 경우보다 많이 사용한 경우 return         if (res <= paperCnt) return;         // 모두 탐색이 끝났을 때         if (idx == N * N) {             // 모든 1을 못 덮었다면             if (oneCnt != 0) return;             // 모든 1을 덮었다면             // 사용한 색종이의 최소 개수 갱신             res = Math.min(res, paperCnt);             return;         }           int r = idx / N;         int c = idx % N;           // 색종이를 붙일수 있는 칸이면         if (map[r][c] == 1) {             // 다섯 종류의 색종이를 붙여보자             for (int p = 5; p >= 1; p--) {                 // 해당 크기 색종이를 모두 사용했으면 pass                 if (paperState[p] == 0) continue;                 // 해당 크기 색종이로 붙일 수 있나 확인                 if (check(r, c, p)) {                     // 붙일 수 있다면 붙이고(oneCnt 감소)                     setPaper(r, c, p, true);                     paperState[p]--;                                          // 다음 위치로                     go(idx + 1, paperCnt + 1);                                          // 돌아오면 다시 스티꺼 떼어내기(oneCnt 증가)                     setPaper(r, c, p, false);                     paperState[p]++;                 }             }         } else {             // 색종이를 붙일 수 없는 경우             go(idx + 1, paperCnt);         }       }       /**      * 실제 색종이를 붙이는 함수      * @param r    행 좌표      * @param c    열 좌표      * @param p    색종이 크기      * @param isPut    색종이를 붙일지, 떼어낼지      */     private static void setPaper(int r, int c, int p, boolean isPut) {           for (int i = 0; i < p; i++) {             for (int j = 0; j < p; j++) {                 // 스티커를 붙일 경우                 if (isPut) {                     // 색종이를 붙이고                     map[r + i][c + j] = 0;                     // 전체 1 개수 감소                     oneCnt--;                 } else {                     // 색종이를 떼어내고                     map[r + i][c + j] = 1;                     // 전체 1 개수 다시 증가                     oneCnt++;                 }             }         }       }       /**      * 해당 색종이로 현재 칸에 붙일 수 있는지 확인      * @param r    행 좌표      * @param c    열 좌표      * @param p    색종이 크기      */     private static boolean check(int r, int c, int p) {           for (int i = 0; i < p; i++) {             for (int j = 0; j < p; j++) {                 // 범위를 벗어날 경우                 if (r + i >= N || c + j >= N) return false;                 // 붙일 자리에 1이 없다면 붙일 수 없음                 if (map[r + i][c + j] != 1) return false;             }         }           return true;     }   } Colored by Color Scripter

cs