네이버 카페에서 발견한 문제.
문제
10*10 칸 즉 100칸의 그랜드체스판이 있습니다
X와 Y좌표를 지정합니다 그리고 그 지점에 나이트(KNIGHT)를 놓습니다 이 나이트를 한 점으로 보고
체스판100칸을 모두 이동할수 있는 로직을 설계하세요~
- 조건 : 반드시 재귀함수를 씁니다. (다른함수로만쓰면 쉽습니다.)
- 상식: 1. 체스는 칸 안에 말을 놓습니다.
2. 나이트는 한턴에 앞으로 한칸 같은방향대각선으로 한칸 진행합니다. (<ex> x+2, y+1 혹은 x-2, y-1 등)
- 힌트 : 1. 나이트는 임의의 한곳에 놓되 return되는 값이 가장 적은곳으로 가야 모든 자리로 돌수 있습니다.
즉, 한나이트가 중심으로부터- /+ 중심에 놓였을때 갈수있는값은 총 8개 입니다
이 8개는 각각 8개씩 퍼져나가고 끝에 이르면 return되어 자기자신에 돌아옵니다. 이것이 재귀함수입니다.
이 반환되는 값을 비교하여 말을 보낸다면 값을구하기에 용이합니다.
2. {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,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,0,0,0,0
}
3. 재귀함수는 여러번 쓰입니다.
실마리
길 찾기 문제와 유사하다. 기본적으로 더 이상 이동할 수 없다면 되돌아가서 다른 방향으로 전환 가능하도록 해야 한다.
소스 코드
소스 코드 보기
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum
{
eNOWAY = 0,
eDONE
};
enum
{
eTOP_RIGHT = 0,
eRIGHT_UP,
eRIGHT_DOWN,
eBOTTOM_RIGHT,
eBOTTOM_LEFT,
eLEFT_DOWN,
eLEFT_UP,
eTOP_LEFT,
eTOTAL_COUNT
};
#ifndef TRUE
#define TRUE (1)
#endif
#ifndef FALSE
#define FALSE (0)
#endif
#ifdef WIN32
#define CONSOLE_CLEAR system("cls")
#elif LINUX
#define CONSOLE_CLEAR system("clear")
#else
#define CONSOLE_CLEAR
#endif
#define LIMIT_MIN_VALUE (1)
#define LIMIT_MAX_VALUE (20)
#define MAX_X (max_x)
#define MAX_Y (max_y)
#define MAX_COUNT ((MAX_X)*(MAX_Y))
#define CARRY_DIGIT (100000000)
#define EMPTY (0)
#define CHECK_INVALID_INPUT(x, y) (((0 < max_x) && (0 < max_y) && \
(LIMIT_MAX_VALUE >= max_x) && (LIMIT_MAX_VALUE >= max_y) && \
(0 <= x) && (max_x > x) && \
(0 <= y) && (max_y > y)) ? TRUE : FALSE)
#define GetHour(sec) ((unsigned int)(sec / 3600))
#define GetMinute(sec) ((unsigned int)((sec % 3600) / 60))
#define GetSecond(sec) ((unsigned int)(sec % 60))
#define CHECK_INVALID_POINT(x, y) (((0 <= x) && (MAX_X > x) && (0 <= y) && (MAX_Y > y)) ? TRUE : FALSE)
#define IS_EMPTY_POINT(x, y) (CHECK_INVALID_POINT(x, y) && (EMPTY == chessBoard[y][x]) ? TRUE : FALSE)
typedef struct _tagCallMoveFuncCount
{
int largeNumber;
int middleNumber;
int smallNumber;
} CALLFUNCCOUNT;
CALLFUNCCOUNT callCount = {0, 0, 0};
unsigned int **chessBoard;
unsigned int moveCount;
int max_x;
int max_y;
void print_chessBoard()
{
int i, j;
printf("재귀 함수 호출 횟수 = %d%08d%08d\n\n",
callCount.largeNumber,
callCount.middleNumber,
callCount.smallNumber);
i = -1;
while (MAX_Y > ++i)
{
j = -1;
while (MAX_X > ++j)
{
printf("%3d ", chessBoard[i][j]);
}
printf("\n\n");
}
}
int check_movable(int _x, int _y, int count, int direction)
{
int x = _x, y = _y;
if ((eTOP_RIGHT > direction) || (eTOTAL_COUNT <= direction))
{
return count;
}
switch (direction)
{
case eTOP_RIGHT: x += 1; y -= 2; break;
case eRIGHT_UP: x += 2; y -= 1; break;
case eRIGHT_DOWN: x += 2; y += 1; break;
case eBOTTOM_RIGHT: x += 1; y += 2; break;
case eBOTTOM_LEFT: x -= 1; y += 2; break;
case eLEFT_DOWN: x -= 2; y += 1; break;
case eLEFT_UP: x -= 2; y -= 1; break;
case eTOP_LEFT: x -= 1; y -= 2; break;
}
if (IS_EMPTY_POINT(x, y))
{
return check_movable(x, y, count + 1, direction);
}
return count;
}
void get_test_result(int _x, int _y, int *result)
{
int x = _x, y = _y;
int test_result[eTOTAL_COUNT];
int *sort_result = result;
int min_idx;
int direction, i, j;
for (direction = eTOP_RIGHT; direction < eTOTAL_COUNT; ++direction)
{
test_result[direction] = check_movable(x, y, -1, direction);
}
for (i = 0; i < eTOTAL_COUNT; ++i)
{
min_idx = eTOP_RIGHT;
for (j = eRIGHT_UP; j < eTOTAL_COUNT; ++j)
{
if (test_result[min_idx] > test_result[j])
{
min_idx = j;
}
}
sort_result[i] = min_idx;
test_result[min_idx] = MAX_COUNT;
}
}
void addRecurrsiveCallCount()
{
if (CARRY_DIGIT == ++callCount.smallNumber)
{
callCount.smallNumber = 0;
if (CARRY_DIGIT == ++callCount.middleNumber)
{
callCount.middleNumber = 0;
++callCount.largeNumber;
}
printf("No.%d%08d%08d 재귀 함수 호출\n",
callCount.largeNumber, \
callCount.middleNumber, \
callCount.smallNumber);
}
}
int doMove(int* const x, int* const y, int direction)
{
if (!x || !y)
{
return FALSE;
}
switch (direction)
{
case eTOP_RIGHT: *x += 1; *y -= 2; break;
case eRIGHT_UP: *x += 2; *y -= 1; break;
case eRIGHT_DOWN: *x += 2; *y += 1; break;
case eBOTTOM_RIGHT: *x += 1; *y += 2; break;
case eBOTTOM_LEFT: *x -= 1; *y += 2; break;
case eLEFT_DOWN: *x -= 2; *y += 1; break;
case eLEFT_UP: *x -= 2; *y -= 1; break;
case eTOP_LEFT: *x -= 1; *y -= 2; break;
}
return IS_EMPTY_POINT(*x, *y);
}
int move_refer_hint(int _x, int _y)
{
int direction;
int x = _x, y = _y;
int sort_result[eTOTAL_COUNT];
int i;
addRecurrsiveCallCount();
get_test_result(x, y, sort_result);
for (i = 0; i < eTOTAL_COUNT; ++i)
{
x = _x;
y = _y;
direction = sort_result[i];
#if TRUE
switch (direction)
{
case eTOP_RIGHT: x += 1; y -= 2; break;
case eRIGHT_UP: x += 2; y -= 1; break;
case eRIGHT_DOWN: x += 2; y += 1; break;
case eBOTTOM_RIGHT: x += 1; y += 2; break;
case eBOTTOM_LEFT: x -= 1; y += 2; break;
case eLEFT_DOWN: x -= 2; y += 1; break;
case eLEFT_UP: x -= 2; y -= 1; break;
case eTOP_LEFT: x -= 1; y -= 2; break;
}
if (IS_EMPTY_POINT(x, y))
#else
if (doMove(&x, &y, sort_result[i]))
#endif
{
chessBoard[_y][_x] = moveCount;
chessBoard[y][x] = ++moveCount;
if ((unsigned int)MAX_COUNT <= moveCount)
{
return eDONE;
}
if (eNOWAY != move_refer_hint(x, y))
{
return eDONE;
}
chessBoard[y][x] = EMPTY;
chessBoard[_y][_x] = --moveCount;
}
}
return eNOWAY;
}
int move(int _x, int _y)
{
int direction;
int x, y;
addRecurrsiveCallCount();
direction = eTOTAL_COUNT;
while (direction--)
{
x = _x;
y = _y;
#if TRUE
switch (direction)
{
case eTOP_RIGHT: x += 1; y -= 2; break;
case eRIGHT_UP: x += 2; y -= 1; break;
case eRIGHT_DOWN: x += 2; y += 1; break;
case eBOTTOM_RIGHT: x += 1; y += 2; break;
case eBOTTOM_LEFT: x -= 1; y += 2; break;
case eLEFT_DOWN: x -= 2; y += 1; break;
case eLEFT_UP: x -= 2; y -= 1; break;
case eTOP_LEFT: x -= 1; y -= 2; break;
}
if (IS_EMPTY_POINT(x, y))
#else
if (doMove(&x, &y, direction))
#endif
{
chessBoard[_y][_x] = moveCount;
chessBoard[y][x] = ++moveCount;
if ((unsigned int)MAX_COUNT <= moveCount)
{
return eDONE;
}
if (eNOWAY != move(x, y))
{
return eDONE;
}
chessBoard[y][x] = EMPTY;
chessBoard[_y][_x] = --moveCount;
}
}
return eNOWAY;
}
int input_int_value(char *question, int min, int max)
{
int value;
printf("%s[%d~%d]? ", question, min, max);
scanf("%d", &value);
while ('\n' != getchar());
return value;
}
int input_yesno_value(char *question)
{
char value;
do
{
printf("%s ", question);
value = getchar();
while ('\n' != getchar());
if (('y' == value) || ('Y' == value) || ('n' == value) || ('N' == value))
{
break;
}
printf("입력 값이 잘못 되었음.\n");
} while (TRUE);
return (('y' == value) || ('Y' == value)) ? TRUE : FALSE;
}
void allocMemory(void)
{
int i;
chessBoard = (unsigned int**)calloc(MAX_Y, sizeof(int*));
if (NULL == chessBoard)
{
printf("Out of memory!\n");
exit(-1);
}
for (i = MAX_Y; i--;)
{
chessBoard[i] = (unsigned int*)calloc(MAX_X, sizeof(int));
if (NULL == chessBoard[i])
{
printf("Out of memory!\n");
exit(-1);
}
}
}
void releaseMemory(void)
{
int i;
for (i = 0; i < MAX_Y; ++i)
{
if (NULL != chessBoard[i])
{
free(chessBoard[i]);
chessBoard[i] = NULL;
}
}
if (NULL != chessBoard)
{
free(chessBoard);
chessBoard = NULL;
}
}
int main(void)
{
int start_x, start_y, result, use_hint;
time_t start_time, processing_time;
moveCount = 1;
CONSOLE_CLEAR;
while (TRUE)
{
max_x = input_int_value("열 개수", LIMIT_MIN_VALUE, LIMIT_MAX_VALUE);
max_y = input_int_value("행 개수", LIMIT_MIN_VALUE, LIMIT_MAX_VALUE);
start_x = input_int_value("시작 x좌표", LIMIT_MIN_VALUE - 1, LIMIT_MAX_VALUE - 1);
start_y = input_int_value("시작 y좌표", LIMIT_MIN_VALUE - 1, LIMIT_MAX_VALUE - 1);
use_hint = input_yesno_value("힌트1을 적용[y/n]?");
if (CHECK_INVALID_INPUT(start_x, start_y))
{
break;
}
printf("입력 허용 범위를 넘긴 값 존재함\n\n");
}
allocMemory();
start_time = time(NULL);
result = (TRUE == use_hint) ? move_refer_hint(start_x, start_y) : move(start_x, start_y);
processing_time = time(NULL) - start_time;
CONSOLE_CLEAR;
printf("\n\n************ %d X %d 크기, 시작 좌표 (%d, %d)의 결과 출력 ************\n\n", MAX_X, MAX_Y, start_x, start_y);
if (eNOWAY == result)
{
printf("모든 칸을 이동하는 방법을 찾지 못했습니다.\n\n");
}
if (0 < processing_time)
{
printf("수행 시간 : %u시간 %u분 %u초(%u초)\n\n", \
GetHour(processing_time), \
GetMinute(processing_time),\
GetSecond(processing_time),\
(unsigned int)processing_time);
}
print_chessBoard();
releaseMemory();
getchar();
return 0;
}
소감
시간이 참 오래 걸리는 문제이다.
코드는 간단한데 10x10 에서는 너무 많은 경우의 수가 발생되어서 왠만큼 시간을 투자하지 않으면 결과를 보기 힘들다.
일단 작은 사이즈에서의 테스트에서는 정상적으로 동작하는 것으로 보아 10x10... 또는 그 이상도 문제 없이 동작할 것으로 생각되나... 테스트를 완료하지 못한 점이 아쉽다.
AMD Phenom 8450 Triple-Core 2.1GHz에서는 10x10으로 크기를 잡아 돌리면 하루 종일 돌려도 계속 진행중이더라...;;
댓글을 달아 주세요
고마워요, 좋은 하루 소원
2012/01/19 18:47