#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 }
};
int chkMap[10][10] = { 0, };
int ROW, COL;
int findWay(int, int, int, int);
void printMap(int(*map)[10]);
void returnValue(int, int, int, int, int*);
bool isChecked = false; // 최종 pos 도착 여부
typedef struct node {
int x;
int y;
int val;
}Node;
int main(void) {
ROW = sizeof(bg) / sizeof(bg[0]);
COL = sizeof(bg[0]) / sizeof(int);
int sum = 0;
for (int x = 0; x < ROW; x++) {
for (int y = 0; y < COL; y++) {
sum += bg[x][y];
}
}
findWay(0, 0, ROW, COL);
////가중치 저장
Node *s = NULL;
for (int x = 0; x < ROW; x++) {
for (int y = 0; y < COL; y++) {
if (chkMap[x][y] > 1) {
if (s != NULL && chkMap[x][y] == s->val) {
for (int y2 = s->y; y2 <= y; y2++) {
chkMap[s->x][y2] = s->val;
}
s = NULL;
}
else {
Node p;
p.x = x;
p.y = y;
p.val = chkMap[x][y];
s = &p;
}
}
}
s = NULL;
//같은 행에서 짝이 맞지 않는경우 s를 초기화
}
for (int y = 0; y < COL; y++) {
for (int x = 0; x < ROW; x++) {
if (chkMap[x][y] > 1) {
if (s != NULL && chkMap[x][y] == s->val) {
for (int x2 = s->x; x2 <= x; x2++) {
chkMap[x2][s->y] = s->val;
}
s = NULL;
}
else {
Node p;
p.x = x;
p.y = y;
p.val = chkMap[x][y];
s = &p;
}
}
}
s = NULL;
}
chkMap[0][0] = chkMap[ROW - 1][COL - 1];
//초기와 끝의 값을 같게 함.
//printMap(chkMap);
int count = chkMap[ROW - 1][COL - 1];
int *list = malloc(sizeof(int) *count);
//길찾기 최대 수 만큼 int 배열 생성
memset(list, 0, sizeof(int) * count);
for (int i = 0; i < count; i++) {
isChecked = false;
returnValue(0, 0, ROW, COL, &list[i]);
}
printMap(bg);
int min = list[0];
for (int i = 1; i < count; i++) {
if (min > list[i]) {
min = list[i];
}
}
printf("전체 길의 수는 %d개이며, 그중 %d가 가장 빠릅니다.\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");
}
free(list);
//메모리 해제
return 0;
}
void returnValue(int x, int y, int xMax, int yMax, int *val) {
if (isChecked) {
return;
}
else {
if (x == xMax-1 && y == yMax-1) {
isChecked = true;
}
*val += bg[x][y];
chkMap[x][y]--;
if (x + 1 < xMax) {
if (chkMap[x + 1][y] > 0) {
returnValue(x + 1, y, xMax, yMax, val);
}
}
if (y + 1 < yMax) {
if (chkMap[x][y + 1] > 0) {
returnValue(x, y + 1, xMax, yMax, val);
}
}
}
return;
}
void printMap(int(*map)[10]) {
//맵 데이터 출력
printf("\n");
for (int x = 0; x < COL; x++) {
for (int y = 0; y < ROW; y++) {
{/*if (map[x][y] == 0) {
printf(" ");
}
else {*/
printf(" %d", map[x][y]);
}
}
printf("\n");
}
}
int findWay(int x, int y, int xMax, int yMax) {
//가중치 생성
int temp;
if (x == xMax && y == yMax) {
chkMap[x][y] += 1;
return -1;
}
else {
if (bg[x + 1][y] && bg[x][y + 1] && bg[x][y]) {
//printf(" %d %d\n", x, y);
//분기되는 부분 출력
chkMap[x][y] += 2;
}
else {
chkMap[x][y] += 1;
}
if (bg[x][y] == 0) {
chkMap[x][y] = 0;
}
else {
if (x + 1 < xMax) {
temp = findWay(x + 1, y, xMax, yMax);
if (temp == -1) {
return -1;
}
}
if (y + 1 < yMax) {
temp = findWay(x, y + 1, xMax, yMax);
if (temp == -1) {
return -1;
}
}
}
}
return 0;
}
직접 풀어보면서 결과를 올린 문제라서 정상적으로 작동한다고는 하지만 모든 경우에 대해서 작동하지 않음. 즉, 현재 맵 데이터를 포함한 일부 맵 데이터에 대해서만 정상적으로 작동하고 그 외에는 오류가 발생하므로 참고용으로만 볼 것
