다익스트라 알고리즘 활용 길찾기 프로그램

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define INT_MAX 2147483647 // 최대 정수
#define TRUE 1
#define FALSE 0
#define NUMBER 8 //정점의 수
#define INF 1000 //무한대(연결이 없는 경우)
#pragma warning(disable:4996)
 
//전역 변수들
int a[8][8]={NULL}; //지역 간 거리들을 2차원 배열로 저장
char city[8][10]={NULL}; // 지역명
int citynum=0;
char cityXY[8][10]={NULL}; // 지역좌표
int distance[NUMBER]; //시작 정점으로부터의 최단 경로 거리
int found[NUMBER]; //방문한 정점 표시
int path[NUMBER][NUMBER]; //최단거리 정점까지 거치는 노드들을 저장
int check[NUMBER];//한 정점으로 가는 정점을 표시
 
 
//함수들
void path_init(int path[][NUMBER]); //path 인접행렬 초기화
int choose(int distance[],int n,int found[]); // 최단거리에 있는 정점을 찾는 함수
void shortest_path(int start, int n);//최단 경로 알고리즘
int distanceInput(); // 지점 간 거리 입력 함수
void inputCity(); // 도시 입력 함수
int search(); // 최단경로 찾기
void menu(); // 실제 메인 메뉴 함수
void disp(); //배열 출력
void citywrite(); //지역, 좌표 파일 저장
void cityread();  //지역, 좌표 파일 읽기
void distancewrite(); // 지점 간 거리 파일 저장
void distanceread();// 지점 간 거리 파일 읽기
 
 
void main()
 
{
    menu();
}
 
 
int distanceInput()
{
    int i=0,j=0,k=0;
    char str1[10]={NULL};
    char str2[10]={NULL};
    int x=0;
    int num=0;
    int count=0;
 
    do{
        printf("지점 사이의 거리 입력:");
        fflush(stdin);
        scanf("%s%s%d",str1,str2,&num);
 
        for(k=0;k<NUMBER;k++)
        {
            if(strcmp(str1,city[k])==0)
            {
                for(i=0;i<NUMBER;i++)
                {
                    if(strcmp(str2,city[i])==0)
                    {
                        a[k][i]=num;
                        a[i][k]=num;
                        count++;
                        break;
                    }
                }
            }
        }
 
        if(count==0)
        {
            printf("입력이 올바르지 않습니다.\n");
            return 0;
        }
 
        printf("한 번 더 입력하려면 1\n입력을 종료하려면 아무키나 누르세요\n");
        scanf("%d",&x);
        while (getchar() != '\n');
 
    }while(x==1);
 
    return 0;
}
 
 
 
 
 
 
 
void inputCity()
{
    int num;
 
    do{
        if(citynum<8)
        {
            printf("지역입력과 x, y좌표입력:(예시:서울 5,8)");
            fflush(stdin);
            scanf("%s%s",city[citynum],cityXY[citynum]); 
 
            citynum++;
            printf("현재 입력 된 지역의 개수 %d개 \n",citynum);
            printf("1. 한 번 더 입력하기\n2. 종료\n");
            scanf("%d",&num);
            while (getchar() != '\n');
        }
        else
        {
            printf("입력실패 지역의 개수는 최대 8개까지 입력가능합니다. \n현재 지역 개수 %d개",citynum);
            num=1;
        }
    }while(num==2);
}
 
//path 인접행렬 초기화
void path_init(int path[][NUMBER])
{
    int i,j;
 
    for(i=0;i<NUMBER;i++)
        for(j=0;j<NUMBER;j++)
            path[i][j] = INF;
}
 
// 최단거리에 있는 정점을 찾는 함수
 
int choose(int distance[],int n,int found[])
{
    int i,min,minpos;
    min = INT_MAX;
    minpos = -1;
 
    for(i=0;i<n;i++)
 
        if(distance[i]<min && !found[i]){
            min = distance[i];
            minpos = i;
        }
        return minpos;
}
 
 
//최단 경로 알고리즘
void shortest_path(int start, int n)
{
    int i,j,u,w;
 
    for(i=0; i<n; i++){//초기화
        distance[i] = a[start][i];
        found[i] = FALSE;
        check[i]=1;
        path[i][0] = start;
    }
 
    found[start] =TRUE;//시작 정점 방문 표시
    distance[start] = 0;
 
    for(i=0; i<n-2; i++){
        u = choose(distance, n, found);
        found[u] = TRUE;
 
        for(w=0; w<n;w++){
            if(!found[w]){
                if(distance[u]+a[u][w] < distance[w]){
                    if(i==0){//처음에는 인접한 정점에 연결
                        path[w][check[w]] = u; //갱신된 경로를 경로 배열에 저장
                        check[w]++;
                    }
                    else{
                        for(j=0; j<(check[u]+1); j++){//저장된 만큼 반복
                            path[w][j] = path[u][j]; //경로를 갱신
                            path[w][j+1] = u; //끝부분에 자기자신을 저장
                            check[w]++;
                        }
                    }
                    distance[w] = distance[u] + a[u][w];
                }
            }
        }
    }
}
 
int search()
{
    int i,j;
    int count1=0,count2=0;
    int start,end;
    char str1[10];
    char str2[10];
 
    path_init(path);
    printf("출발지와 도착지를 입력하세요:");
    scanf("%s%s",str1,str2);
 
    for(i=0;i<NUMBER;i++)
    {
        if(strcmp(str1,city[i])==0)
        {
            start=i;
            count1++;
        }
 
        if(strcmp(str2,city[i])==0)
        {
            end=i;
            count2++;
        }
    }
 
    if(count1==0)
    {
        printf("출발지를 잘 못 입력하셨습니다.\n");
        return 0;
    }
 
    if(count2==0)
    {
        printf("도착지를 잘 못 입력하셨습니다.\n");
        return 0;
    }
    printf("\n");
    shortest_path(start,NUMBER);
 
    printf("%s에서 %s까지의 최단거리 : %d \n",city[start],city[end],distance[end]);
    printf("%s에서 %s까지의 노 드 : ",city[start],city[end]);
 
    for(j=0; j<NUMBER; j++){
        if(path[end][j]!=INF){
            printf("%s->", city[path[end][j]]);//저장된 경로를 출력한다
        }
    }
    printf("%s\n\n",city[end]);
    return 0;
}
 
 
void menu()
{
    int i,j,num;
    printf("-----------------------------\n");
    printf("\t메인 화면\n");
    printf("-----------------------------\n\n");
    printf("최대 8개의 지역까지 입력 가능합니다.\n");
    printf("1. 지역,좌표 입력\n");
    printf("2. 지역 간 거리 입력\n");
    printf("3. 최단 경로 찾기\n");
    printf("4. 지역, 좌표 파일에 저장하기\n");
    printf("5. 지역 간 거리 파일에 저장하기\n");
    printf("6. 현재 입력된 지역과 거리 확인\n");
    printf("7. 프로그램 종료\n");
    printf("원하시는 기능의 번호를 입력하세요:");
 
    scanf("%d",&num);
    while (getchar() != '\n');
 
    switch (num)
    {
    case 1: 
        num=0;
        printf("1. 지역, 좌표 직접 입력하기\n");
        printf("2. 지역, 좌표 파일로 불러오기\n주의! 파일의 처음부터 최대 8개까지만 불러옵니다. 8개가 넘을 경우 파일의 데이터가 누락될 수 있습니다.\n");
        scanf("%d",&num);
        while (getchar() != '\n');
 
        if(num==1)
        {
            inputCity();
        }
        else if(num==2)
        {
            cityread();
        }
        else
        {
            printf("입력이 올바르지 않습니다.\n");
        }
        break;
 
    case 2: 
        num=0;
        printf("1. 지역 간 거리 직접 입력하기\n");
        printf("2. 지역 간 거리 파일로 불러오기\n주의! 덮어쓰기입니다. 현재 입력된 거리 데이터가 사라집니다.\n");
        scanf("%d",&num);
        while (getchar() != '\n');
 
        if(num==1)
        {
            distanceInput();
            for(i=0;i<8;i++)
            {
                for(j=0;j<8;j++)
                {
                    if(i!=j && a[i][j]==0)
                    {
                        a[i][j]=INF;
                    }
                }
                printf("\n");
            }
        }
        else if(num==2)
        {
            distanceread();
        }
        else
        {
            printf("입력이 올바르지 않습니다.");
        }
        break;
 
    case 3:search(); break;
    case 4: citywrite(); break;
    case 5:    distancewrite(); break;
    case 6: disp(); break; 
    case 7:
        printf("프로그램을 종료합니다.");
        exit(1); break;
 
    default: printf("입력이 올바르지 않습니다.");
        break;
 
    }
    printf("\n\n\n");
    menu();
}
 
 
void disp()
{
    int i,j;
 
    for(i=0;i<NUMBER;i++)
    {
        printf("%s %s\n",city[i],cityXY[i]);
    }
 
    for(i=0;i<NUMBER;i++)
    {
        for(j=0;j<NUMBER;j++)
        {
            printf("%d\t",a[i][j]);
        }
        printf("\n");
    }
}
 
 
 
void citywrite()
 
{
    FILE *fp;
    FILE *fp2;
 
    fopen_s(&fp,"city.txt","w");
    fopen_s(&fp2,"cityXY.txt","w");
 
    for(int i=0;i<NUMBER;i++)
    {
        fprintf(fp,"%s ",city[i]);
        fprintf(fp2,"%s ",cityXY[i]);
    }
    fclose(fp);
    fclose(fp2);
}
 
 
 
void cityread()
{
    FILE *fp;
    FILE *fp2;
    char strTemp[255];
    char *ptr;
    int i=0;
    int temp;
    temp=citynum;
 
    fp=fopen("city.txt","r");
    fp2=fopen("cityXY.txt","r");
 
    fgets(strTemp,255,fp);
    ptr=strtok(strTemp," ");
 
    while(ptr!=NULL && citynum<8)
 
    {
        strcpy(city[citynum],ptr);
        ptr=strtok(NULL," ");
        citynum++;
    }
 
    fclose(fp);
 
    printf("city.txt 지역 파일 불러 오기 성공\n");
 
    citynum=temp;
    fgets(strTemp,255,fp2);
    ptr=strtok(strTemp," ");
 
    while(ptr!=NULL && citynum<8)
    {
        strcpy(cityXY[citynum],ptr);
        ptr=strtok(NULL," ");
        citynum++;
    }
    fclose(fp2);
 
    printf("cityXY.txt 지역 파일 불러 오기 성공\n");
 
}
 
 
void distancewrite()
{
    FILE *fp;
    int i,j;
    fopen_s(&fp,"distance.txt","w");
 
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            fprintf(fp,"%d ",a[i][j]);
        }
        fprintf(fp,"\n");
    }
    fclose(fp);
}
 
void distanceread()
{
    FILE *fp;
    int i,j;
 
    fp = fopen("distance.txt", "r+");
 
    for (i = 0; i < 8; i++)
    {
        for (j = 0; j < 8; j++)
        {
            fscanf(fp, "%d", &a[i][j]);
        }
    }
    fclose(fp);
    printf("distance.txt 지역 간 거리 파일 불러 오기 성공\n");
}