static int D, W, K;
static int board[13][20];
static int injection[13];
static int ans;
static bool find_ans;
static bool check(int (*tmp)[20])
{
bool ret = true;
for (int x = 0; x < W && ret; x++)
{
int priv = tmp[0][x], cnt = 1;
for (int y = 1; y < D && cnt < K; y++)
{
if (tmp[y][x] == priv) //실수한 부분
cnt += 1;
else
{
priv = tmp[y][x]; //실수한 부분
cnt = 1;
}
}
if (cnt != K)
ret = false;
}
return ret;
}
static void __solution(int y, int cnt)
{
if (y >= D || cnt == ans)
{
int cpy[13][20];
for (int cy = y; cy < D; cy++)
injection[cy] = 2;
memcpy(cpy, board, sizeof(board));
for (int cy = 0; cy < D; cy++)
{
if (injection[cy] < 2)
{
for (int x = 0; x < W; x++)
cpy[cy][x] = injection[cy];
}
}
if (check(cpy))
find_ans = true;
}
else
{
for (int i = 0; i <= 2 && !find_ans; i++)
{
if (cnt < ans)
{
injection[y] = i;
if (injection[y] < 2) //실수한 부분
__solution(y + 1, cnt + 1);
else //실수한 부분
__solution(y + 1, cnt);
}
else
{
injection[y] = 2;
__solution(y + 1, cnt);
}
}
}
}
static int solution(void)
{
scanf("%d %d %d", &D, &W, &K);
for (int y = 0; y < D; y++)
{
for (int x = 0; x < W; x++)
{
scanf("%d", &board[y][x]);
}
}
if (check(board))
return 0;
find_ans = false;
ans = 0;
while (!find_ans)
{
ans += 1;
if (ans == D)
break;
__solution(0, 0);
}
return ans;
}전체적인 흐름은 다음과 같다.
먼저 입력을 받고, 입력 받은 자체만으로 제시된 조건을 만족할 경우 약품을 별도로 투입 하지 않아도 되므로 바로 0을 반환, 그렇지 않으면 약품 투입 횟수를 늘려나가면서 확인 하는데, 투약 횟수가 입력의 전체 깊이가 되면 더 이상 확인하지 않고 해당 값을 반환한다.
여기서 주어진 board가 주어진 조건의 만족 여부는 check()를 통해 이루어 지는데,
K만큼의 연속된 값이 각 열 마다 있으면 최종적으로 true를 반환하고, 중간에 K만큼의 연속된 값이 있지 않다면 false를 반환 하는 것이다.
다음은 __solution()에 대한 것이다.
해당 함수는 재귀 함수로 구현하여 특정 위치에 어떤 값을 주입 할 지에 대한 모든 경우를 만들어 내고, 이 후 변경된 board가 주어진 조건을 만족하는지 확인하는데,
두가지 실수한 부분이 있었다.
첫번째는 주입할 모든 경우를 만들어 내는데 있었다. 먼저 solution()에서 주입횟수를 원하는 만큼 정한 뒤, 이 함수를 호출하게 되는데, 여기서 cnt가 0 또는 1, 즉, A, B중 어떤 값으로 주입되었는지 그 개수를 알려준다.
그래서 cnt < ans 보다 작다면 0 또는 1 이라는 값이 선택되었기에 재귀 호출 시 cnt + 1 을 하였는데, 여기서 문제가 있었다. cnt < ans 보다 작아도 반복문 특성 상 2(변경하지 않는다)라는 값이 설정 될 수 있다.
두번째 실수한 부분은 check()에서 인자로 전달 받은 배열을 대상으로 조건 만족 여부를 확인하여야 하는데, 처음에 코드를 작성할 때 board로 체크하도록 되어 있었다. 즉, injection에 따라 변경된 배열을 대상을 매개변수로 넘겨 봤자 해당 함수는 이를 대상으로 판단하는 것이 아닌 원래 배열을 대상으로 참조하기 때문에 ans를 끝까지 가는 경우가 답으로 출력되었다.
이 두가지 실수를 수정하여 패스를 할 수 있었으나, 실행시간 측면에서 만족스럽지 못했다.
5초 중 거의 3.1초가 걸렸기 때문이다. 이와 같은 결과가 발생한 이유는 첫번재로 injection시 불 필요한 값이 설정되는 경우와, 재귀의 끝마다 전체 배열을 복사한 후 수정하고 check 하기 때문으로 판단하였다.
그래서 위 두가지를 보완하여 다음과 같이 __solution() 만 수정하였다.
static void __solution(int y, int cnt)
{
if (y >= D || cnt == ans)
{
if (cnt < ans) //주입할 위치를 원하는 만큼 정하지 못한 경우,
return;
if (check())
find_ans = true;
}
else if (D - y < ans - cnt) //충분히 주입할 위치를 정하지 못한 경우
return;
else
{
for (int i = 0; i <= 2 && !find_ans; i++)
{
if (cnt < ans)
{
injection[y] = i;
if (injection[y] < 2)
{
int org[20]; //back up
memcpy(org, board[y], sizeof(board[y])); //stored
for (int x = 0; x < W; x++)
board[y][x] = injection[y]; //1의 경우 memset() 사용 시, 제대로 초기화 되지 않음,
__solution(y + 1, cnt + 1);
memcpy(board[y], org, sizeof(org)); //recover
}
else
__solution(y + 1, cnt);
}
else
{
injection[y] = 2;
__solution(y + 1, cnt);
}
}
}
}위 코드의 경우 603ms로 2.5초 정도의 성능 향상이 있음을 확인 할 수 있었다.
D - y < ans - cnt 에 대해서만 간단히 정리하면
주입할 위치를 4개 정해야 한다 가정하고, D값이 10이고 현재 y가 8이다. 그런데 아직까지도 주입할 위치가 정해지지 않았다면 그 밑으로는 더 이상 재귀를 돌면서 위치를 정할 필요가 없다. 이 경우 굳이 더 확인할 필요도 없기 때문에
더 이상 재귀를 호출하지 않는 것이다.
