[C++] 백준(BOJ) - 17136 : 색종이 붙이기
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.
종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.
입력
총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.
출력
모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.
알고리즘
- 완전탐색
- 백트래킹
풀이
- 큰 색종이부터 붙일 생각 (Heuristic method)
- 탐색하지 않을 지점은 탐색하지 않는다 (백트래킹)
코드
// BOJ - 17136 : 색종이 붙이기
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int n = 10, a[20][20], res = INF;
map<int, int> mp;
bool check(int y, int x, int cnt)
{
if (y + cnt > n || x + cnt > n) return false;
for (int i = y; i < y + cnt; i++)
{
for (int j = x; j < x + cnt; j++)
{
if (a[i][j] == 0) return false;
}
}
return true;
}
void draw(int y, int x, int cnt, int val)
{
for (int i = y; i < y + cnt; i++)
{
for (int j = x; j < x + cnt; j++)
{
a[i][j] = val;
}
}
}
void dfs(int y, int x, int cnt)
{
if (cnt >= res) return; // 최소값 찾기, 백트래킹 (탐색할 필요 없는 지점은 탐색하지 않는다)
if (x == n)
{
dfs(y + 1, 0, cnt);
return;
}
// 기저사례
if (y == n)
{
res = min(res, cnt);
return;
}
if (a[y][x] == 0)
{
dfs(y, x + 1, cnt);
return;
}
for (int _size = 5; _size >= 1; _size--)
{
if (mp[_size] == 5) continue; // 각 색종이 개수 5개 제한
if (check(y, x, _size)) // 색종이를 붙일 수 있는지
{
// 완전탐색의 기본꼴
mp[_size]++;
draw(y, x, _size, 0);
dfs(y, x + _size, cnt + 1);
draw(y, x, _size, 1);
mp[_size]--;
}
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
dfs(0, 0, 0);
if (res == INF) cout << -1 << '\n';
else cout << res << '\n';
return 0;
}
평가
- 구현문제의 경우 문제를 이해하고 차근차근 로직을 짜가는 과정이 중요
- DFS 탐색으로 안되는 문제는 없다
- 어려워보여도 조건 설정, 로직, 반례 찾기 순으로 차근차근 해보기
