문제
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
<그림 1>
색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.
종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.
입력
총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.
출력
모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.
로직은 간단한 DFS였으나 런타임이 자꾸 발생하였다.
그 이유 . 기본적으로 DFS 탐색이라 하면 새로운 current 값에서 공통 자원을 탐색하는 게 주요 로직인데
만약 런타임이 발생한다면 , 같은 인덱스를 다시 참조할 필요가 있는지 생각해 보아야 한다.
색종이 같은 경우 자신의 위치에서 1이 존재한다면 각 5가지의 케이스에서 가능한 경우 붙이고 붙인 상태의
종이판을 다음 차례에서 또 붙이기 위해 참조 할 때, 이미 붙여진 자리까지 또 참조할 필요가 없다.
이 부분에서 어마어마한 시간이 소요되기 때문에 하나의 인덱스에서 작업이 끝나면 같은 인덱스는 두번다시 보지 않도록 설계 해야 함.
for문으로 방문하지 않은 지점인 경우 DFS를 진행해라 하는 경우 같은 로직이 될 수 도 있겠으나 , 어쨌든 탐색을 하면서 조건 비교를 해야 한다는 점.
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
같은 상황에서
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
왼쪽 위가 1로만 5개가 먼저 채워졌다고 생각해보자 그럼 그 다음 DFS에서 마지막 1이 다시 빈자리로 리셋되고
for이 또 처음부터 돌기 때문에 그 빈자리를 다시 1이 채우고 또 5개를 다썼으니 그다음 DFS에서 빈자리가 되고
또 처음부터 돌기 때문에 또 채우고 무한 반복이 된다.
#include<iostream>
using namespace std;
int arr[10][10];
int size = 0;
bool visit[10][10];
int paper[5];
int mina = 987654321;
bool normal = false;
void DFS(int cur,int i, int j)
{
if(j == 10)
{
DFS(cur,i+1,0);
}
if(i == 10)
{
if(size == 0)
{
normal = true;
if(mina > cur)
{
mina = cur;
}
return;
}
}
if(arr[i][j] && !visit[i][j])
{
if(paper[0] > 0)
{
if(i < 10 && j <10)
{
int mul = 1;
bool flag = false;
for(int k = 0; k < 1; k++)
{
for(int l = 0; l < 1; l++)
{
mul *= arr[i+k][j+l];
if(visit[i+k][j+l])
{
flag = true;
break;
}
}
}
if(!flag && mul)
{
for(int k = 0; k < 1; k++)
{
for(int l = 0; l < 1; l++)
{
visit[i+k][j+l] = true;
}
}
paper[0]--;
size -= 1;
DFS(cur+1,i,j+1);
size += 1;
paper[0]++;
for(int k = 0; k < 1; k++)
{
for(int l = 0; l < 1; l++)
{
visit[i+k][j+l] = false;
}
}
}
}
}
if(paper[1] > 0)
{
if(i+1 < 10 && j+1 <10)
{
int mul = 1;
bool flag = false;
for(int k = 0; k < 2; k++)
{
for(int l = 0; l < 2; l++)
{
mul *= arr[i+k][j+l];
if(visit[i+k][j+l])
{
flag = true;
break;
}
}
}
if(!flag && mul)
{
for(int k = 0; k < 2; k++)
{
for(int l = 0; l < 2; l++)
{
visit[i+k][j+l] = true;
}
}
paper[1]--;
size -= 4;
DFS(cur+1,i,j+1);
size += 4;
paper[1]++;
for(int k = 0; k < 2; k++)
{
for(int l = 0; l < 2; l++)
{
visit[i+k][j+l] = false;
}
}
}
}
}
if(paper[2] > 0)
{
if(i+2 < 10 && j+2 <10)
{
int mul = 1;
bool flag = false;
for(int k = 0; k < 3; k++)
{
for(int l = 0; l < 3; l++)
{
mul *= arr[i+k][j+l];
if(visit[i+k][j+l])
{
flag = true;
break;
}
}
}
if(!flag && mul)
{
for(int k = 0; k < 3; k++)
{
for(int l = 0; l < 3; l++)
{
visit[i+k][j+l] = true;
}
}
paper[2]--;
size -= 9;
DFS(cur+1,i,j+1);
size += 9;
paper[2]++;
for(int k = 0; k < 3; k++)
{
for(int l = 0; l < 3; l++)
{
visit[i+k][j+l] = false;
}
}
}
}
}
if(paper[3] > 0)
{
if(i+3 < 10 && j+3 <10)
{
int mul = 1;
bool flag = false;
for(int k = 0; k < 4; k++)
{
for(int l = 0; l < 4; l++)
{
mul *= arr[i+k][j+l];
if(visit[i+k][j+l])
{
flag = true;
break;
}
}
}
if(!flag && mul)
{
for(int k = 0; k < 4; k++)
{
for(int l = 0; l < 4; l++)
{
visit[i+k][j+l] = true;
}
}
paper[3]--;
size -= 16;
DFS(cur+1,i,j+1);
size += 16;
paper[3]++;
for(int k = 0; k < 4; k++)
{
for(int l = 0; l < 4; l++)
{
visit[i+k][j+l] = false;
}
}
}
}
}
if(paper[4] > 0)
{
if(i+4 < 10 && j+4 <10)
{
int mul = 1;
bool flag = false;
for(int k = 0; k < 5; k++)
{
for(int l = 0; l < 5; l++)
{
mul *= arr[i+k][j+l];
if(visit[i+k][j+l])
{
flag = true;
break;
}
}
}
if(!flag && mul)
{
for(int k = 0; k < 5; k++)
{
for(int l = 0; l < 5; l++)
{
visit[i+k][j+l] = true;
}
}
paper[4]--;
size -= 25;
DFS(cur+1,i,j+1);
size += 25;
paper[4]++;
for(int k = 0; k < 5; k++)
{
for(int l = 0; l < 5; l++)
{
visit[i+k][j+l] = false;
}
}
}
}
}
}
else
{
DFS(cur,i,j+1);
}
}
int main(void)
{
for(int i = 0; i < 10; i++)
{
for(int j = 0; j <10; j++)
{
cin >> arr[i][j];
if(arr[i][j] == 1)
{
size++;
}
}
}
for(int i = 0; i < 5; i++)
{
paper[i] = 5;
}
DFS(0,0,0);
if(normal)
{
cout << mina << endl;
}
else
{
cout << -1 << endl;
}
}'Algorithm' 카테고리의 다른 글
| 백준 17471번 게리맨더링 (삼성 A형) (0) | 2020.03.06 |
|---|---|
| 백준 17406번 배열 돌리기 4 (삼성 A형) (0) | 2020.03.05 |
| 백준 17135번 캐슬 디펜스 (삼성 A형) (0) | 2020.03.03 |
| 백준 17070번 파이프 옮기기 1 (삼성 A형) (0) | 2020.03.02 |
| 백준 16637번 괄호 추가하기 (삼성 A형) (0) | 2020.03.01 |
