• 출제의도 출제자가 평소에 자주 즐기는 퍼즐입니다 ㅇ<-<
• 문제풀이 이번에 입력으로 주어진 데이터들은 모두 'Trial and Error' 를 거치지 않고서도 풀 수 있는 데이터였습니다. (라고 책에 나와있습니다) 그런데 생각하고 있는 알고리즘을 모두 구현하기가 쉽지 않아서 결국은 Trial-and-Error로 풀게 되었지요 :< 하지만 모든 경우에 대해서 무작정 Back-Tracking 기법을 사용하는것보다는 확실히 정해진 일부 칸들을 먼저 구합니다. 예를 들어 두 칸이 비어있는데 합이 16인 경우라면 (7, 9) 이외의 숫자는 해당 칸에 사용할 수가 없는 식으로요. 이런식으로 어떤 칸에 사용할 수 없는 숫자들을 테이블로 미리 구해둔다면 꽤나 많은 경우의 수가 단축됩니다. 저는 우선 이정도의 처리만 했는데요, 좀 더 다양한 알고리즘이 존재하니 도전해 보시면 좋을 듯 합니다 :D
• 소스코드 ~~~ cpp

#include
#include
using namespace std;
struct elem
{
int x, y, rc, sum;
};
struct BACKUP_STATE
{
int _allow[30][30];
vector > _table;
};
bool found;
int allow[30][30];
vector allcase[46][10];
int bit[46][10];
vector > state[30][30];
vector > table;
vector data;
vector conn[30][30]; // 현재 좌표에 영향을 미치는 data의 index
vector btable;
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int N, M;
FILE *in = stdin;
void backup()
{
BACKUP_STATE tmp;
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= N; ++j)
tmp._allow[i][j] = allow[i][j];
tmp._table = table;
btable.push_back(tmp);
}
void load()
{
BACKUP_STATE tmp = btable[btable.size() - 1];
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= N; ++j)
allow[i][j] = tmp._allow[i][j];
table = tmp._table;
}
void recover()
{
BACKUP_STATE tmp = btable[btable.size() - 1];
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= N; ++j)
allow[i][j] = tmp._allow[i][j];
table = tmp._table;
btable.pop_back();
}
void init()
{
for (int i = 1; i < (1 << 9); ++i)
{
vector tmp;
int sum = 0;
int cn = 0;
for (int j = 0; j < 9; ++j)
if (i & (1 << j))
{
sum += (j + 1);
cn++;
}
allcase[sum][cn].push_back(i);
bit[sum][cn] |= i;
}
}
void input()
{
fscanf(in, "%d", &N);
table.assign(N + 1, vector (N + 1, -1));
memset(allow, 0, sizeof(allow));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
{
fscanf(in, "%d", &table[i][j]);
if (table[i][j] == 1) allow[i][j] = (1 << 9) - 1;
table[i][j]--;
conn[i][j].clear();
}
fscanf(in, "%d", &M);
data.resize(M);
for (int i = 0; i < M; ++i)
{
fscanf(in, "%d %d %d %d", &data[i].x, &data[i].y, &data[i].rc, &data[i].sum);
data[i].x--;
data[i].y--;
}
}
int GetCount(int x, int y, int rc, int &must, int &mustnot)
{
int ret = 0;
for (;;)
{
x += dx[rc];
y += dy[rc];
if (table[x][y] != -1)
{
ret++;
if (table[x][y] != 0)
{
must |= (1 << (table[x][y] - 1));
mustnot |= (1 << (table[x][y] - 1));
}
}
else
{
break;
}
}
return ret;
}
int go(int sum, int remain, int must, int mustnot)
{
int ret = bit[sum][remain] - mustnot;
int bitmask = 0;
for (int i = 0; i < allcase[sum][remain].size(); ++i)
{

if ((must & allcase[sum][remain][i]) == must)
{
bitmask |= allcase[sum][remain][i];
}
}
return ret & bitmask;
}
void greedy1()
{
for (int i = 0; i < M; ++i)
{
int x = data[i].x, y = data[i].y;
int rc = data[i].rc, sum = data[i].sum;
int must = 0, mustnot = 0;
int gc = GetCount(x, y, rc, must, mustnot);
for (;;)
{
x += dx[rc], y += dy[rc];
if (table[x][y] == -1) break;
allow[x][y] &= go(sum, gc, must, mustnot);
}
}
}
bool isFinish()
{
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (table[i][j] == 0) return false;
return true;
}
bool find(int x, int y, int v)
{
v++;
for (int i = 0; i < 4; ++i)
{
int xx = x, yy = y;
for (;;)
{
xx += dx[i], yy += dy[i];
if (table[xx][yy] == -1) break;
if (table[xx][yy] == v) return true;
}
}
return false;
}
bool set()
{
bool ret = false;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (table[i][j] == 0)
{
if ((allow[i][j] & (allow[i][j] - 1)) == 0)
{
for (int k = 0; k < 9; ++k)
if (allow[i][j] & (1 << k))
{
if (!find(i, j, k))
{
table[i][j] = k + 1;
ret = true;
}
}
}
}
}
}
return ret;
}
void backtr(int x, int y)
{
if (found) return;
while (!isFinish())
{
greedy1();
if (!set()) break;
}
if (isFinish())
{
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
printf("%d", max(table[i][j], 0));
if (j != N - 1) printf(" ");
}
printf("\n");
}
found = true;
return;
}
backup();
for (;;)
{
y++;
if (y == N) { y = 0, x++; }
if (table[x][y] == 0) break;
}
for (int i = 0; i < 9; ++i)
{
if ((allow[x][y] & (1 << i)) != 0)
{
table[x][y] = i + 1;
backtr(x, y);
table[x][y] = 0;
load();
}
}
recover();
}
int main()
{
init();
int T;
fscanf(in, "%d", &T);
while (T--)
{
btable.clear();
input();
found = false;
backtr(0, 0);

}
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/50134">원문보기</a>]</div>