#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
int bg[][10] = {
{ 8,9,5,4,3,8,6,3,2,0 },
{ 3,0,0,0,2,0,0,0,1,0 },
{ 2,0,0,0,5,0,0,0,5,0 },
{ 3,1,5,0,4,0,0,0,7,0 },
{ 0,0,7,0,2,0,0,0,3,0 },
{ 0,0,3,0,1,0,0,0,2,9 },
{ 0,0,2,0,1,9,5,0,0,3 },
{ 0,0,2,0,0,0,4,3,0,1 },
{ 0,0,1,0,0,0,0,8,0,8 },
{ 0,0,5,8,6,3,2,2,6,6 }
};
#pragma region STRUCUTRE
typedef struct _Pos {
int x;
int y;
}Pos;
typedef struct _node {
int value;
int totalValue;
struct _node *xNode;
struct _node *yNode;
struct _Pos *pos;
}Node;
#pragma endregion
#pragma region FUNCTIONS
void setyNode(Node *n, Node *yNode) {
if (n->yNode != NULL) {
setyNode(n->yNode, yNode);
}
else {
n->yNode = yNode;
}
return;
}
void setxNode(Node *n, Node *xNode) {
if (n->xNode != NULL) {
setxNode(n->xNode, xNode);
}
else {
n->xNode = xNode;
}
return;
}
Node *setNode(int value, Pos *p) {
Node *n = (Node *)malloc(sizeof(Node));
n->pos = (Pos *)malloc(sizeof(Pos));
n->xNode = n->yNode = NULL;
n->value = value;
n->totalValue = n->value;
n->pos->x = p->x;
n->pos->y = p->y;
return n;
}
void DestroyNode(Node *n) {
if (n->xNode != NULL) {
DestroyNode(n->xNode);
}
if (n->yNode != NULL) {
DestroyNode(n->yNode);
}
free(n->pos);
free(n);
return;
}
void findNode(Node *, Pos *, Pos *);
void printMap(int[][10]);
int searchNode(Node *, Pos *);
void returnValue(Node *, Pos *, int *, int *, int);
#pragma endregion
int ROW, COL;
Node *root;
//root Node
int main(void) {
#pragma region Initialization
ROW = sizeof(bg) / sizeof(bg[0]);
COL = sizeof(bg[0]) / sizeof(int);
root = (Node *)malloc(sizeof(Node));
root->pos = (Pos *)malloc(sizeof(Pos));
root->xNode = root->yNode = NULL;
root->pos->x = 0;
root->pos->y = 0;
root->value = bg[root->pos->x][root->pos->y];
root->totalValue = root->value;
#pragma endregion
Pos *end = (Pos *)malloc(sizeof(Pos));
end->x = ROW - 1;
end->y = COL - 1;
findNode(root, root->pos, end);
printMap(bg);
int count = 0;
count = searchNode(root, end);
int i = 0;
int *list = (int *)malloc(sizeof(int) *count);
memset(list, 0, sizeof(int) * count);
returnValue(root, end, list, &i, count);
int min = list[0];
for (int i = 1; i < count; i++) {
if (min > list[i]) {
min = list[i];
}
}
printf("길의 총 개수는 %2d개이며, 가장 빠른 길은 %3d 입니다.\n",count, min);
printf("전체 길 경로 : \n");
for (int i = 0; i < count; i++) {
printf("\t%d : %d", i + 1, list[i]);
if (list[i] == min) {
printf(" >> 1순위");
}
printf("\n");
}
DestroyNode(root);
free(end);
free(list);
return 0;
}
void findNode(Node *parent, Pos *start, Pos *end) {
if (bg[start->x][start->y]) {
Pos *Nxt = (Pos *)malloc(sizeof(Pos));
if (start->x + 1 <= end->x) {
if (bg[start->x + 1][start->y]) {
Nxt->x = start->x + 1;
Nxt->y = start->y;
parent->xNode = setNode(bg[Nxt->x][Nxt->y], Nxt);
parent->xNode->totalValue += parent->totalValue;
findNode(parent->xNode, Nxt, end);
}
}
if (start->y + 1 <= end->y) {
if (bg[start->x][start->y + 1]) {
Nxt->x = start->x;
Nxt->y = start->y + 1;
parent->yNode = setNode(bg[Nxt->x][Nxt->y], Nxt);
parent->yNode->totalValue += parent->totalValue;
findNode(parent->yNode, Nxt, end);
}
}
free(Nxt);
}
}
void printMap(int map[][10]) {
for (int x = 0; x < ROW; x++) {
for (int y = 0; y < COL; y++) {
printf("%2d ", bg[x][y]);
}
printf("\n");
}
}
int searchNode(Node *root, Pos *p) {
int count = 0;
if (root->xNode != NULL) {
count += searchNode(root->xNode, p);
}
if (root->yNode != NULL) {
count += searchNode(root->yNode, p);
}
return count + !(memcmp(root->pos, p, sizeof(Pos)));
}
void returnValue(Node *root, Pos *p, int *list,int *index, int maxLength) {
if (root->xNode != NULL) {
returnValue(root->xNode, p, list, index, maxLength);
}
if (root->yNode != NULL) {
returnValue(root->yNode, p, list, index, maxLength);
}
if (!(memcmp(root->pos, p, sizeof(Pos))) && ((*index) < maxLength)) {
list[*index] = root->totalValue;
(*index)++;
}
return;
}
기존의 코드는 모든 맵 데이터에 작용하지 않는 것이 눈에 보였으나, 이번 코드는 눈으로 보기에는 코드상 오류가 없어보임. 즉, 모든 맵 데이터에 대해서 정상적으로 작동될 것으로 예상됨.
