static int N;
static int board[20][20];
static int table[101];
static int d[4][2] = {
1, 1,
1, -1,
-1, -1,
-1, 1
};
static bool can_go(int y, int x)
{
if (y < 0 || y >= N)
return false;
if (x < 0 || x >= N)
return false;
if (table[board[y][x]])
return false;
return true;
}
static int travel(int y, int x)
{
int ret = -1;
for (int vert = 2; vert < N; vert++)
{
for (int hori = 2; hori < N; hori++)
{
if (vert + hori - 1 > N)
break;
int cy = y, cx = x, cnt = 0;
int lens[] = { hori, vert, hori, vert };
bool is_fail = false;
memset(table, 0, sizeof(table));
for (int dir = 0; dir < 4 && !is_fail; dir++)
{
int len;
for (len = 1; len < lens[dir]; len++)
{
int ny = cy + d[dir][0];
int nx = cx + d[dir][1];
if (!can_go(ny, nx))
{
is_fail = true;
break;
}
cy = ny;
cx = nx;
table[board[cy][cx]] = 1;
cnt += 1;
}
}
if (!is_fail)
{
if (cnt > ret)
ret = cnt;
}
}
}
return ret;
}
static int solution(void)
{
int ret = -1, v = 0;
scanf("%d", &N);
for (int y = 0; y < N; y++)
{
for (int x = 0; x < N; x++)
scanf("%d", &board[y][x]);
}
for (int y = 0; y < N - 2; y++)
{
for (int x = 1; x < N - 1; x++)
{
if ((v = travel(y, x)) > ret)
ret = v;
}
}
return ret;
}이차원 배열에서 대각선 방향으로만 움직일 수 있을때, 중복된 수 없이 시작 위치로 돌아올 수 있을 때, 그 원소 개수를 구하는 문제이다.
여기서 중요한 점은 배열의 순환을 사각형 형태로 한다는 점이다.
사실 이 부분이 엄청난 힌트가 된다. 왜냐하면 얼마만큼 이동 할 수 있을 지 정할 수 있기 때문이다.
처음에 풀이해본 방식은 현재 위치에서 해당 방향으로 얼마나 계속 이동 할 수 있는지 살펴보고, 더 이상 이동 할 수 없으면 가장 마지막에 위치했던 부분에서 방향을 틀어 이동하는 식으로 구현을 해보았다.
그러나 이 경우에는 사각형으로 배열을 순환 할 수 없는 구조도 있었다.
이 경우에는 시작 위치 1에서 시작 하지만 다시 돌아 올 수는 없다. 물론 반복이 끝나는 조건을 시작 위치로 돌아올 때 까지로 놓고 돌아 올 수 없는 경우면 경로 정보가 저장된 스택에서 pop하여 다시 탐색하는 구조로 작성하기는 했지만,
샘플 테스트케이스 전부를 맞추진 못했고, 틀린 테스트 케이스에서 N의 값이 20이었기 때문에 디버깅 하면서 틀린 부분을 찾기란 쉽지 않았다.
그래서 사각형이라는 조건이 매우 중요한 것이다. 위 경우와 같은 것을 생각할 필요가 없기 때문이다.
먼저 solution()에서 시작 정점을 잡는 것에 대해서,
시작 정점이 될 수 없는 곳은 아래와 같다.
자기 자신으로 돌아 올 수 없고, 최소 길이를 만족하지 못하는 부분들은 시작 정점의 후보가 될 수 없다.
마지막은 시작 정점에서 순회하는 부분에 대한 것이다.
첫번째는 밑변, 높이가 배열을 초과하는 부분에 대해서는 탐색할 필요가 없다.
두번째는 순회를 할 때에 시작정점을 visit하지 않는 것이다. 이는 마지막으로 되돌아 올 때 조건 검사에서 걸러지지 않게 하기 위함이다.
마지막은 첫번째로 방향전환이 일어나는 부분에 대해서 해당 정점부터 그 길이를 1로 하는 것이다.
이는 코드의 간결함을 위해서이다. 밑변부분에 포함되는 정점이 3개이면 마지막 정점을 높이부분에 포함시키지 않는 식으로 코드를 작성하면 이 부분에 대한 처리가 방향이 바뀔 때 매번 처리를 해주어야 한다.
그러나 이렇게 해주면 중복되는 듯이 보여도 코드를 작성하기에는 훨씬 수월한 면 이 있다.
