이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 53 번째 글 입니다.
목차
골드3 : 완전탐색 문제이다. 삼성 A형 기출이다.
생각
시간이 1초라, 제한 시간에 들어올 수 있는지 시간 복잡도 계산부터 진행했다. 최악의 경우 100개의 공간에 모두 1이 차있는 경우 한 개의 공간에서 색종이를 5번 검사해야 한다.
백트래킹을 해야 하나 고민했지만, 다행히 이 문제의 경우 한 개의 공간에서 5개의 경우의 수가 무조건적으로 발생하지 않는다는 점을 고려하여 풀이를 진행했다. 구현에 앞서 중요하게 생각한 것들은 다음과 같다.
- 종이의 수는 5장이다. 이 부분을 업데이트 해준다.
- 칠했다는 것을 표현하고, 이 부분은 탐색을 하지 않는다.
- 칠할 수 없는 곳은 칠하지 않고 다음 옵션으로 넘어간다.
- 끝나는 조건은 모든 1이 색칠이 되었을 때이다.
설계
main
입력을 받는다.
이 때, 입력이 1인 경우 이 위치만 저장한다.
1의 개수를 저장해 둔다.
탐색한다.
탐색 후 값을 출력한다.
탐색 함수
만약 현재까지 칠한 개수가 1의 개수와 같다면 answer를 업데이트 한다.
현재 depth의 1의 위치를 가져온다.
이 위치에 색종이가 붙어있지 않다면
5개의 색종이를 순차적으로 비교한다. 이 때 큰 색종이 부터 탐색한다.
만약 현재 색종이가 남아있다면
만약 해당 색종이를 붙일 수 있다면
색종이를 칠한다
색종이의 개수를 하나 감소시킨다
색종이를 붙이고, 다음 위치에서 탐색한다.
색종이의 개수를 하나 증가시킨다
색종이를 뗀다
색종이를 붙일 수 없다면
다음 색종이를 탐색한다
현재 색종이가 남아있지 않다면
다음 색종이를 탐색한다
이 위치에 색종이가 붙어있다면
다음 위치에서 탐색한다.
Code
// 골드3 : 백준 17136번 색종이 붙여넣기
#include <iostream>
#include <vector>
#define INF 2000000000
using namespace std;
int globalAns = INF, N = 0;
int map[10][10] = {0};
vector<pair<int, int>> position;
pair<int, int> action[5] = {make_pair(5, 5),
make_pair(4, 5),
make_pair(3, 5),
make_pair(2, 5),
make_pair(1, 5)};
void fillSquare(int y, int x, int num, int value){
for (int i = y; i < y+num; i++)
for (int j = x; j < x+num; j++)
map[i][j] = value;
}
bool isFillPossible(int y, int x, int num){
for (int i = y; i < y+num; i++) {
for (int j = x; j < x+num; j++) {
if (!(0 <= i && i < 10 && 0 <= j && j < 10)) return false;
if (map[i][j] == 0 || map[i][j] == 2) return false;
}
}
return true;
}
void go(int depth, int localAns, int paint){
if (paint == N) {
globalAns = min(globalAns, localAns);
return;
}
int y = position[depth].first, x = position[depth].second;
if (map[y][x] == 1) {
for (int i = 0; i < 5; i++) {
int squareSize = action[i].first, &squareCount = action[i].second;
if (squareCount != 0) {
if (isFillPossible(y, x, squareSize)) {
fillSquare(y, x, squareSize, 2);
squareCount--;
go(depth+1, localAns+1, paint+(squareSize*squareSize));
squareCount++;
fillSquare(y, x, squareSize, 1);
}
} else continue;
}
} else go(depth+1, localAns, paint);
}
int main(){
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
cin >> map[i][j];
if (map[i][j] == 1) position.push_back(make_pair(i, j));
}
}
N = int(position.size());
go(0, 0, 0);
if (globalAns == INF) {
if (position.size() == 0) cout << 0;
else cout << -1;
}
else cout << globalAns;
cout << '\n';
return 0;
}