최대 길이가 12인 정사각형의 보드 위에 코어가 최대 12개까지 있을 수 있을 때, 이들을 연결하는 최소 비용을 구하는 문제입니다.
실제 삼성 공채 시험 SW 역량 테스트 난이도와 비슷한 수준이라고 볼 수 있습니다. 문제에서 요구하는 것을 정리하면 다음과 같습니다.
1) 모든 코어는 반드시 전부 연결 될 필요는 없다.
2) 코어가 많이 연결될 수록 유리하다.
3) 같은 개수의 코어가 연결될 경우엔 가장 짧은 길이로 연결을 해야 한다.
그리고 문제에서 주어진 조건으로는
-셀의 모서리 부분에 위치한 코어는 이미 연결된 것으로 간주한다.
가 있습니다.
얼핏 생각했을 때는 이 문제를 어떻게 접근해야 할 지 감이 오지 않습니다. 내가 어떤 셀을 특정 방향으로 연결함으로써 다른 셀의 기회비용을 날리는 것은 아닌지, 어떠한 규칙성이 존재하여 특정 규칙을 만족하는 셀의 분포는 배치를 다르게 해준다는 등 많은 생각을 해 볼 수 있습니다.
하지만 우리는 프로그램을 이용해 문제를 푸는 만큼, 프로그램만이 가능한 접근 방법으로 생각해 볼 수 있습니다.
코어는 최대 12개 까지 있을 수 있으며, 상하좌우 직선으로만 연결할 수 있는 판에서, 연결할 수 있는 모든 경우의 수를 계산하면
$4^{12} = 16777216$ 가지가 존재할 수 있습니다. 인간이 일일이 세기에는 굉장히 큰 숫자이지만, 프로그램이 따져보기에는 상당히 작은 숫자임을 알 수 있습니다. 따라서 이 문제는 정말 모든 경우를 다 체크해 보는 방법으로 접근할 수 있습니다. 그러면, 어떻게 문제를 접근할 수 있을까요? 여기서는 재귀적 기법을 활용한 깊이 우선 탐색(DFS)을 하려고 합니다. 함수는 다음과 같이 정의할 수 있습니다.
$dfs(P, Q, R)$ : 현재 P번째 코어를 확인해 볼 차례이며, 지금까지 Q개의 코어가 연결되었고, 그 비용은 R이다.
만약 P번째 코어가 추가 비용이 들지 않는 모서리에 연결되어 있다면
$dfs(P, Q, R)$ => $dfs(P+1,Q+1,R)$ 로 넘어갈 수 있습니다.
그 이외에는 어떤 경우가 있을까요? 해당 코어를 상, 하, 좌, 우로 연결하는 경우와, 연결하지 않고 다음 코어를 확인하는 경우가 있습니다.
단, 모서리에 있는 코어는 어떠한 경우에도 연결하는 것이 유리하므로 연결하지 않거나 4방향을 확인해보지 않고 바로 넘어간다면 시간을 단축시킬 수 있을 것입니다.
특정 방향으로 연결할 때 드는 비용을 S라고 한다면
$dfs(P, Q, R)$ => $dfs(P+1, Q+1, R+S)$ 로 가며 연결하지 않는다면
$dfs(P, Q, R)$ => $dfs(P+1, Q, R)$ 로 갈 수 있습니다. 시간복잡도는 $O(4^n)$ 입니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<stdio.h>
int n, core[12][2], corePtr, board[12][12], dir[4][2] = { { -1,0 },{ 0,1 },{ 1,0 },{ 0,-1 } }, cmp, ans=2e9;
bool visited[12][12];
void init()
{
ans = 2e9, cmp = 0, corePtr = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 2; j++) core[i][j] = 0;
for (int j = 0; j < n; j++) core[i][j] = visited[i][j] = 0;
}
}
void dfs(int pos, int cnt, int val)
{
if (pos == corePtr)
{
if (cmp < cnt)
{
cmp = cnt;
ans = val;
}
else if(cmp == cnt)
ans = ans > val ? val : ans;
return;
}
if (core[pos][0] == 0 || core[pos][0] == n - 1 || core[pos][1] == 0 || core[pos][1] == n - 1)
{
dfs(pos + 1, cnt + 1, val);
return;
}
for (int i = 0; i < 4; i++)
{
int nx = core[pos][0], ny = core[pos][1], len = 0;
bool f = true;
while (1)
{
nx += dir[i][0], ny += dir[i][1];
if (nx < 0 || ny < 0 || nx == n || ny == n) break;
if (visited[nx][ny])
{
f = false;
break;
}
visited[nx][ny] = true;
len++;
}
if (f) dfs(pos + 1, cnt + 1, val + len);
while (nx - dir[i][0] != core[pos][0] || ny - dir[i][1] != core[pos][1])
{
nx -= dir[i][0], ny -= dir[i][1];
visited[nx][ny] = false;
}
}
dfs(pos + 1, cnt, val);
}
int main()
{
int T;
scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &board[i][j]);
if (board[i][j] == 1)
visited[i][j] = true, core[corePtr][0] = i, core[corePtr][1] = j, corePtr++;
}
}
dfs(0, 0, 0);
printf("#%d %d\n", tc, ans);
init();
}
}