[BOJ / C++] 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을 출력한다.

Solved.ac 레벨

골드 II 

문제 풀이 과정

백트래킹 문제다.

 

백트래킹에서는 가지치기 및 유효성 검사가 매우 중요한데, 이 문제에서 내가 사용한 가지치기 조건은 아래와 같다.

 

1. 현재 선택 위치에 색종이를 붙일 수 있으면 탐색한다. 그 외에는 탐색을 종료한다. (graph[i][j] == 1 인 경우 -> 붙일 수 있다)
2. 색종이 크기는 1 x 1, 2 x 2, 3 x 3, 4 x 4, 5 x 5의 다섯가지로, 큰 것 부터 사용한다. (그리디하게 가보자는 마인드)
   
   1. 이를 위해 색종이의 크기를 미리 배열로 만들어두었다.
3. 현재까지 사용한 색종이 수가 최솟값보다 작을 때만 탐색한다. (필요한 색종이의 최솟값을 구해야 하므로)

이를 이용하여 백트래킹을 진행한 방식은 아래와 같다.

if(graph[row][col] == 1) {
// grpah[row][col]은 1이므로 색종이를 붙일 수 있다.

        for(int i = 5; i >= 1 ; i--) {
        // 색종이의 갯수만큼 반복한다.
            if(paper[i] > 0 && check(row, col, i)) {
                paper[i]--; // 색종이 사용
                fill(row, col, i, 0); // 색종이 붙이기
                backtracking(idx + 1, paperCnt + 1);
                paper[i]++;
                fill(row, col, i, 1); // 색종이 떼기
            }
        }
    } else {
    	// 붙일 수 없다면 인덱스를 옮겨 재귀 호출로 재탐색
        backtracking(idx + 1, paperCnt);
    }

 

 check 함수의 경우 탐색할 (row, col)이 범위 내에 있는지, 탐색 조건에 부합하는지... 일반적으로 DFS나 BFS에서 다음 탐색 노드를 평가할 때 쓰는 그 구문이 담겨있다.

 

fill 함수는 색종이를 해당 노드에 붙이고 떼는 처리를 담당한다. 붙이기의 경우 0으로 변경하여 해당 위치에 더이상 색종이를 붙일 수 없음을 나타내고 떼기의 경우 1로 변경하여 다시 그 자리에 색종이를 붙일 수 있도록 나타낸다.

 

void fill(int r, int c, int paperSize, int flag) {
    for(int i = r; i < r + paperSize; i++) {
    	// 색종이는 정사각형이므로 각 행, 열에 + 색종이 한 변의 크기로 만들어주면 됨!
        for(int j = c; j < c + paperSize; j++) {
                graph[i][j] = flag;
        }
    }
}

 

 

 

문제 풀이 코드

 

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graph(10, vector<int>(10)); // 그래프
vector<int> paper = {0, 5, 5, 5, 5, 5}; // 사용 가능한 색종이 개수
int result = INT_MAX; // 최솟값 저장
void backtracking(int idx, int paperCnt); // (x, y) 좌표, 종이 사용 카운트
bool check(int x, int y, int paperSize); // 색종이 붙일 수 있는가?
void fill(int x, int y, int paperSize, int flag); // 색종이 붙이기 (그래프 0 -> 1)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            cin >> graph[i][j];
        }
    }

    // 탐색은 색종이를 붙일 수 있는 1번째 위치를 찾는 것으로 시작한다.
    // 왼쪽 위 -> 오른쪽 -> 오른쪽 끝 -> 왼쪽 위
    backtracking(0, 0);

    if(result == INT_MAX) {
        cout << -1 << "\n";
    } else {
        cout << result << "\n";
    }

    return 0;
}

// 가지 치기 조건
// 1. 현재 선택 위치에 색종이를 붙일 수 있는가? (1인가?)
// 2. 색종이 크기는 5가지고, 큰 것부터 사용한다.
// 3. 붙일 수 없다면 탐색을 종료한다.
// 4. 현재까지 사용한 색종이 수가 최솟값보다 크다면 탐색을 종료한다.
void backtracking(int idx, int paperCnt) {
    if(idx == 100) {
        // 좌표 끝일 때의 처리
        result = min(result, paperCnt);
        return;
    }

    int row = idx / 10;
    int col = idx % 10;
    

    // 현재까지 사용한 색종이 수가 최솟값보다 크거나 같다면 탐색 종료
    if(result <= paperCnt) return;

    if(graph[row][col] == 1) {
        for(int i = 5; i >= 1 ; i--) {
            if(paper[i] > 0 && check(row, col, i)) {
                paper[i]--; // 색종이 사용
                fill(row, col, i, 0); // 색종이 붙이기
                backtracking(idx + 1, paperCnt + 1);
                paper[i]++;
                fill(row, col, i, 1); // 색종이 떼기
            }
        }
    } else {
        backtracking(idx + 1, paperCnt);
    }
}

bool check(int r, int c, int paperSize) {
    if(r + paperSize > 10 || c + paperSize > 10) return false;

    for(int i = r; i < r + paperSize; i++) {
        for(int j = c; j < c + paperSize; j++) {
            if(graph[i][j] == 0) return false;
        }
    }

    return true;
}

void fill(int r, int c, int paperSize, int flag) {
    for(int i = r; i < r + paperSize; i++) {
        for(int j = c; j < c + paperSize; j++) {
                graph[i][j] = flag;
        }
    }
}

 

문제 링크

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