[Algorithm/C++17] 백준 17136 색종이 붙이기

문제

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

17136번: 색종이 붙이기

풀이 방법

(0,0)부터 시작해서 (10,10)까지 종이에 1이 적혀있으면 큰 색종이부터 작은 색종이까지 붙일 수 있는 종이를 다 붙혔다 뗐다하면서(백트래킹) 깊이 우선 탐색을 한다.

2580번 스도쿠와 비슷할 수도 있는 문제.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int answer = 0x6FFFFFFF;
void dfs(vector<vector<bool>> &v, vector<int> &paper, int y, int x, int count)
{
	// 다 붙혔을때보다 색종이 개수가 더 많이 필요하다면 가지치기
    if(count >= answer) return; 
    // 현재 열 탐색 완료, 다음 행으로
    if(x == 10)
    {
        dfs(v, paper, y+1, 0, count);
        return;
    }
    // 모든 행 탐색 완료, 개수 갱신
    if(y == 10)
    {
        answer = count;
        return;
    }
    // 칸에 0이 적혀있으면 색종이 붙일 필요 없음, 다음 열로
    if(v[y][x] == 0)
    {
        dfs(v, paper, y, x+1, count);
        return;
    }
    
    for(int i=4; i>=0; i--)
    {
    	// 색종이가 없거나 현재 종이위치보다 색종이가 더 클 경우 다른 색종이로 시도
        if(paper[i] == 0 || y+i+1 > 10 || x+i+1 > 10) continue;
        
		// 현재 크기의 색종이로 1이 적혀있는 칸만 덮을 수 있는지 확인
        // 덮는 범위 안에 0이 적혀있는 칸이 있으면 다른 색종이로 시도
        bool cover = true;
        for(int j=y; j<y+i+1 && cover; j++)
        {
            for(int k=x; k<x+i+1; k++)
            {
                if(v[j][k] == 0)
                {
                    cover = false;
                    break;
                }
            }
        }
        if(!cover) continue;
        
        // 색종이로 덮기
        for(int j=y; j<y+i+1; j++)
        {
            for(int k=x; k<x+i+1; k++)
            {
                v[j][k] = false;
            }
        }
        // 사용 가능한 개수 차감하고 계속 탐색 진행
        paper[i]--;
        dfs(v, paper, y, x, count+1);
        // 탐색 완료되었으면 상태를 되돌림
        for(int j=y; j<y+i+1; j++)
        {
            for(int k=x; k<x+i+1; k++)
            {
                v[j][k] = true;
            }
        }
        paper[i]++;
    }
}
int main()
{
    vector<vector<bool>> v(10, vector<bool>(10, false));
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            int t;
            scanf("%d", &t);
            v[i][j] = t;
        }
    }
    vector<int> paper(5, 5);
    dfs(v, paper, 0, 0, 0);
    if(answer == 0x6FFFFFFF) printf("-1");
    else printf("%d", answer);
    return 0;
}

고찰

백트래킹으로 풀어야 한다는걸 미리 알고 있는 상태에서 문제를 접해서 꽤 할만했던 문제. 모르고 봤으면 그리디로 풀 수도 있었는데 다른 분들 풀이 보니 그리디로는 해결하지 못하는 케이스가 몇 개 있었다.

paper[0]에 1x1 색종이, paper[1]에 2x2 색종이, paper[2]에 3x3 색종이... 식으로 저장했기 때문에,

for문에서 paper[i]의 범위를 처리할때 y ~ y+i+1로 해야하는 것만 조심하자.