[Algorithm] BOJ 17136 색종이 붙이기

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

17136 색종이 붙이기

---

문제

<그림 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을 출력한다.

예제

---

풀이

---

생각

• 처음 문제를 봤을 때, '색종이의 최소 개수'를 구하는 것이니 큰 것(5x5)부터 붙일 수 있는가 확인하면서 붙이는 과정을 수행하면 되는 것이라고 생각했다. (그리디 하게 푸는 방법)

  • 이렇게 생각하니, 한 10분만에 코드를 완성한 것 같다.
  • 당연히, 이렇게 생각하면 안된다....

• 안되는 이유는 큰 것 부터 붙이는 것은 최적의 수를 구하는 것이 아니기 때문이다.

  • 큰 것부터 붙이게 되면 애매하게 남는 경우가 생긴다. 아래의 예제가 있다 하자.
    
  • 큰 것부터 붙이게 되면 다음과 같이 수행되어, 1x1 색종이가 부족해 결국엔 불가능(-1)으로 결론이 나게 된다.
    
  • 최적의 답이라고 하면 다음과 같이 수행될 수 있을 것이다.
    

• 이 것뿐 아니라, 붙일 수 있는 상황이 되더라도 최적의 답이 나오지 않는 수가 존재한다.

  • 예제는 이 블로그를 확인 !

• 결론적으로 이 문제는 백트랙킹 + 완전탐색으로 풀어야 하는 문제가 된다.

  • 모든 경우를 다 살피되, 현재까지 구한 최소 필요 색종이 수보다 큰 경우로 진행되는 부분은 포기하는 형식으로 !

방법

• 먼저, 인풋으로 입력 값들을 받으면서 '색종이를 붙일 수 있는 공간'을 vector에 저장해놓는다.
• solution 함수를 통해 탐색을 수행한다.
  • num: 현재까지 붙인 색종이 수
  • change: 현재까지 붙인 면적
• 만약 vector size와 change가 같다면,
  • 현재까지의 결과 res와 num을 비교하여 더 작은 수를 res에 넣는다. (결과 업데이트)
• 만약 num이 res보다 크면,
  • 이 과정은 최소 색종이 수를 넘어선 것이므로, 더 수행할 필요가 없다. -> 종료한다.
• vector 데이터를 탐색한다.
  • 이전 과정에서 이미 색종이가 붙여졌다면, 넘어간다.
  • 아니라면, 남은 색종이 중 제일 큰 색종이부터 붙여본다.
    • 붙일 수 있다면, 붙이고 색종이 개수를 줄여준다. 그리고 num과 change를 알맞게 증가시켜 다시 solution을 호출한다. 그리고 붙인 것을 다시 제거해준다. 그리고 색종이 크기를 줄여가며 다시 반복.
• vector 데이터 탐색 시, 색종이가 붙지 않은 첫 번째 vector 데이터를 다 수행하고 나왔다면 다음 vector로 넘어가지 않고 종료한다.
  • 여길 넘어간다는 것은 첫 번째 vector의 공간에는 색종이를 붙이지 않는 것이 되니, 더 수행할 필요가 없다.

유의

• 백트랙킹에서는 역시 조건을 잘 세워서 필요 없는 경우의 수를 계산하지 않도록 하는 것이 매우 중요한 것 같다.
  • 현재까지 붙인 색종이 수가 최소 색종이 수보다 큰 가?
  • 이미 색종이가 붙었는가?
  • 색종이 수가 충분한가?
  • 모든 공간에 색종이를 붙이고 있는가?
• 처음 res 값은 충분히 큰 값이여야 한다.
  • 이 문제의 경우, 최대 색종이 수가 25개로 제한되어 있으므로 26으로 초기화하면 된다.
• colored 2차원 배열을 따로 두어 색종이를 붙였는가를 확인했다.
  • vector로 접근해서 이미 붙인 공간에 대한 것을 어떻게 확인할 것인가? 이거에 대해서 새로운 배열을 둬 확인했다고 생각하면 될 듯.

---

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#define bb ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
struct point {
    int x, y;
};
vector<point> vec;
int m[11][11], colored[11][11];
int cpaper[6] = { 5, 5, 5, 5, 5, 5 }; // 하나 버림
int res = 26; // 최대 결과 25이므로, 그것보다 큰 값을 둔다

// 붙일 수 있는지 확인
bool check(int& x, int& y, int& bound) {
    for (int a = x; a < x + bound; ++a) {
        for (int b = y; b < y + bound; ++b) {
            if (a > 9 || b > 9) return false;    // 범위 오버
            if (colored[a][b]) return false;    // 이미 붙여졌으면, 붙일 수 없음
            if (!m[a][b]) return false;            // 붙일 수 없는 곳
        }
    }
    return true;
}

void glue(bool go, int& x, int& y, int& bound) {
    if (go) {
        // 붙이기
        for (int a = x; a < x + bound; ++a) {
            for (int b = y; b < y + bound; ++b) {
                colored[a][b] = 1;
            }
        }

    }
    else {
        // 제거하기
        for (int a = x; a < x + bound; ++a) {
            for (int b = y; b < y + bound; ++b) {
                colored[a][b] = 0;
            }
        }
    }
}

void solution(int num, int change) {
    if (vec.size() == change) { 
        // 다 붙인 경우
        res = min(res, num);
        return;
    }
    if (num >= res) return; // 현재 최소값보다 크면, 더 할 필요 없다.

    for (int i = 0; i < vec.size(); ++i) {
        point present = vec[i];
        if (colored[present.x][present.y]) continue;
        for (int j = 5; j > 0; --j) {
            if (cpaper[j] < 1) continue;
            if (check(present.x, present.y, j)) {
                // 색종이 붙이기
                glue(true, present.x, present.y, j);
                cpaper[j]--;

                // 재귀
                solution(num + 1, change + (j*j));

                // 색종이 제거
                glue(false, present.x, present.y, j);
                cpaper[j]++;
            }
        }
        /*
        여길 통과한다는 것은 이번 vec[i]에는 색종이를 붙이지 않는다는 것.
        즉, -1이 나올 수 밖에 없다. 그러니 종료.
        */
        return; 

    }
}

int main() {
    bb;
    // input
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            cin >> m[i][j];
            if (m[i][j]) vec.push_back({ i, j });
        }
    }

    solution(0, 0);

    if (res > 25) cout << -1 << '\n';
    else cout << res << '\n';


    return 0;
}

---

느낀점

• 문제를 보곤 저어엉말 쉬운 문제구나 생각했다. 그냥 큰거 비교하면 되는거 아님!? 했기 때문에...
  • 정말 쉽다고 생각하는 것도 마음속에 여유를 두게 한다.
  • 하지만 그게 제대로 되지 않을 때 충격은 훨씬 더 크다.
• 색종이가 붙지 않은 첫 번째 vector 값을 수행하고, 넘어갈 때 다음 vector 값을 수행해야하는가? 여기서 엄청 많은 생각을 했다.
  • 왜 시간이 오바가 될까, 이걸 넘어가면 안되나?
  • 현재 과정으로 봤을 때, 이 하나의 값을 색칠하지 않고 넘어간 것이기 때문에 여길 넘어간 결론은 최종적으로 -1이 될 수 밖에 없다는 것을 생각하면 됬다...
• 백트래킹은 그지같이 복잡한 것 같다. 아직 많은 문제를 풀지 않아서기도 한 데, 요즘은 머리가 잘 안돌아간다는 생각이 많이들어서 더 힘든 것 같다.
  • 여기서 이걸 넣고 dfs식으로 돌아가는 것이니깐, 다음 연산에 대해 생각하지 않고 새로 함수에 들어간다고 생각해야하는데... 계속 아 이거 끝나면 다음연산은 어떻게 수행되지 이런 생각으로 다 계산을 하고 있으니깐 그러는 것 같다.
  • 이런 과정들은 템플릿 화해서 암기해 풀어가는게 좋은 것 같다.

---

참조

• https://www.acmicpc.net/problem/17136
• https://2jinishappy.tistory.com/40