C언어 지하철 최단경로 - ceon-eo jihacheol choedangyeonglo

전에 알고리즘에 올렸던 지하철 최단거리를 C언어로 구현해 보았습니다.

어떻게 구현할지에 대해서 생각이 되어있다보니 구현을 하기까지 그렇게 어렵지는 않았습니다.

일단 최단경로에 주로 쓰이는 다익스트라 알고리즘을 사용하였습니다.

하지만 이 프로그램에 메인은 지하철역간을 걸어가서 운동하는 시간을

추가하는 것인데요. 프로그램의 제목이기도한 30분 걷기라는 주제로

도착시간과 소요시간을 고려하여 어디부터 어디까지 걸어라는 식으로 표시하게 만들었습니다.

원래 시작은 버스로 구현하기로 하였지만 하고하고하던중 버스 구현에는 오랜 시간이 소모되고

능력이 약간 부족하여 일단 쉬운 지하철로 구현을 하게 되었습니다.

dat 파일은 역간 소요시간 및 역간 거리 정보를 일일이 따왔습니다.

아래 소스 첨부합니다.

20171201 추가

 관련소스 압축 첨부합니다. 이게 맞는지 기억이 안나요 ;;ㅜㅜ

//******************************************
//* 제작 : 이종근                           *
//* 최종 작성일 : 2011-08-21                *
//* 프로그램 이름 : 30분 걷기 지하철 Ver.    *
//******************************************

#include <stdio.h>
#include <windows.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <time.h>
#include <dos.h>
#include "Station.h"

#define TRUE   1
#define FALSE  0
// 정거장수
#define NODES  227  
// 연결되지 않은 노드
#define INF    999   
extern char transfer[12][25];
extern char _1st[98][25];
extern char _2st[51][25];
extern char _3st[43][25];
extern char _4st[48][25];

// 네트워크의인접행렬
int station[NODES][NODES];
double stationDis[NODES][NODES];

// 시작노드로부터의 최단거리
int Distance[NODES];
// 경유노드
int path[NODES];
// 방문한 노드 표시
int found[NODES];
// 출발역 도착역
int num1, num2;
double walk;
// 출발역 계산을 위한 변수
int endSig, startCode;

int choose(int [], int, int []);
void shortest_path(int, int [][NODES], int [], int n, int []);
void print_path(int, int);
void createSubway();
void createSubwayDis();
void display();
void startStation(double, int, int, int);

void main()
{
 display();
}

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 cost[][NODES], int Distance[], int n, int found[]) /* 시작노드start  */
{ 
 int i, u, j;
 for(i=0; i<n; i++) /* 초기화*/
 {
  Distance[i] = cost[start][i];
  path[i] = start;
  found[i] = FALSE;
 }
 found[start] = TRUE;    /* 시작노드방문표시*/
 Distance[start] = 0;
 for(i=0; i<n; i++){
  //             print_distance();
  u = choose(Distance, n, found);
  if(u == -1)
   break;
  found[u] = TRUE;
  for(j=0;j<n; j++)
   if(!found[j])
    if( Distance[u]+cost[u][j] < Distance[j]) {
     Distance[j] = Distance[u]+cost[u][j];
     path[j] = u;           /* 경유노드저장*/
    }
 }
}
//경로 출력
void print_path(int start, int end)
{ 
 int i, j, k, line1[4], line2[4], count1, count2, trans;
 char temp[25], temp1[25], temp2[25], a[100], b[100];
 if( path[end] != start)
  print_path(start, path[end]);
 for( i = 0 ; i < NODES ; i++) {
  if(path[end] == i)
   strcpy(a,StationName(i));
  if(end == i)
   strcpy(b,StationName(i));
 }
 // 환승하는지 검사 후 환승이면 출력
 strcpy(temp, StationName(path[end]));
 for( i = 0 ; i < ( sizeof(transfer) / sizeof(transfer[0])) ; i++ ) {
  if(strcmp(temp, transfer[i]) == 0) {
   strcpy(temp1, StationName(end));
   strcpy(temp2, StationName(path[path[end]]));
   count1 = 0;
   for( j = 0; j < (sizeof(_1st) / sizeof(_1st[0])) ; j++) {
    if(strcmp(temp1, _1st[j]) == 0 ) {
     line1[count1] = 1;
     count1++;
     break;
    }    
   }
   for( j = 0; j < (sizeof(_2st) / sizeof(_2st[0])) ; j++) {
    if(strcmp(temp1, _2st[j]) == 0 ) {
     line1[count1] = 2;
     count1++;
     break;
    }
   }
   for( j = 0; j < (sizeof(_3st) / sizeof(_3st[0])) ; j++) {
    if(strcmp(temp1, _3st[j]) == 0 ) {
     line1[count1] = 3;
     count1++;
     break;
    }
   }
   for( j = 0; j < (sizeof(_4st) / sizeof(_4st[0])) ; j++) {
    if(strcmp(temp1, _4st[j]) == 0 ) {
     line1[count1] = 4;
     count1++;
     break;
    }
   }

   count2 = 0;
   for( j = 0; j < (sizeof(_1st) / sizeof(_1st[0])) ; j++) {
    if(strcmp(temp2, _1st[j]) == 0 ) {
     line2[count2] = 1;
     count2++;
     break;
    }
   }
   for( j = 0; j < (sizeof(_2st) / sizeof(_2st[0])) ; j++) {
    if(strcmp(temp2, _2st[j]) == 0 ) {
     line2[count2] = 2;
     count2++;
     break;
    }
   }
   for( j = 0; j < (sizeof(_3st) / sizeof(_3st[0])) ; j++) {
    if(strcmp(temp2, _3st[j]) == 0 ) {
     line2[count2] = 3;
     count2++;
     break;
    }
   }
   for( j = 0; j < (sizeof(_4st) / sizeof(_4st[0])) ; j++) {
    if(strcmp(temp2, _4st[j]) == 0 ) {
     line2[count2] = 4;
     count2++;
     break;
    }
   }
   for( j = 0 ; j < count1 ; j++ ) {
    for( k = 0 ; k < count2; k++ ) {
     if(line1[j] == line2[k] ) {
      trans = 1;
      break;
     }
    }
   }

   if ( trans != 1) {
    printf("(환승) ");
   }
   //printf("%d %d %d %d %d %d ", line1[1], line1[0], line2[1], line2[0], count1, count2);
  } 
 }
 // 경로출력
 if(path[end] == start) {
  printf(" %s (출발) ", a);
  printf(" %s ", b);
 }
 else if( path[end] != start)
  printf(" %s ", b); 
}
// Data 파일생성 (시간)
void createSubway() {
 FILE *fp;
 int i, j, temp;
 // 파일 오픈
 fp = fopen("subway.dat", "rt");
 if(fp == NULL) {
  printf("\tLoad Error !! \n");
  getch();
  return;
 }
 for ( i = 0 ; i < NODES ; i++ ) {
  for( j = 0 ; j <NODES ; j++) {
   fscanf(fp, "%d ", &temp);
   if(temp == -1)
    station[i][j] = INF;
   else 
    station[i][j] = temp;
  }
 }
}

// Data 파일생성(거리)
void createSubwayDis() {
 FILE *fp;
 int i, j;
 double temp;
 // 파일 오픈
 fp = fopen("DisDat.dat", "rt");
 if(fp == NULL) {
  printf("\tLoad Error !! \n");
  getch();
  return;
 }
 for ( i = 0 ; i < NODES ; i++ ) {
  for( j = 0 ; j <NODES ; j++) {
   fscanf(fp, "%lf ", &temp);
   if(temp == -1.0)
    stationDis[i][j] = INF;
   else 
    stationDis[i][j] = temp;
  }
 }
}
void display(){
 char cont = 'Y', temp[10];
 char start[20], end[20];
 createSubway();
 createSubwayDis();
 // 시간정보 구조체
 struct tm *d;
 time_t curr;

 int cHour, cMin, dHour, dMin, dTime, lastHour, lastMin;
 double walkDistance;
 

while(cont == 'Y' || cont == 'y' ){
  printf("\n\n                    30분걷기 프로그램 ver. 지하철!!(1~4호선)\n\n");

     // 현재 시간 출력 및 도착시간 입력
  curr=time(NULL);
  d=localtime(&curr);
  printf("현재시간 :");
  printf("%d년%d월%d일 ", d->tm_year+1900, d->tm_mon+1, d->tm_mday);
  cHour = d->tm_hour;
  cMin = d->tm_min;
  printf("%d시%d분\n", cHour, cMin);
  printf("도착시간을 입력해 주세요(ex 13시 50분): ");
  scanf("%d %s %d", &dHour, temp, &dMin);
  fflush(stdin);
  while( cHour >= dHour ) {
   if(cHour > dHour) {
    printf("도착시간을 다시 입력해 주세요(ex 13시 50분): ");
    scanf("%d %s %d", &dHour, temp, &dMin);
    fflush(stdin);
   }
   else if(cHour == dHour) {
    if(cMin < dMin)
     break;
    if(cMin >= dMin) {
     printf("도착시간을 다시 입력해 주세요(ex 13시 50분): ");
     scanf("%d %s %d", &dHour, temp, &dMin);
     fflush(stdin);
    }
   }
  }
  // 도착시간까지 남은 시간 구하기
  if(cHour < dHour) {
   dTime = (dHour - cHour - 1) * 60;
   dTime += dMin;
   dTime += 60-cMin;
  }
  else if(cHour == dHour) {
   dTime = dMin - cMin;
  }

     printf("\n출발역 이름을 입력하세요.(1~4호선) : ");
  scanf("%s", start);
  num1 = StationCode(start);
  while(num1 == -1) {
   printf("\n출발역 이름을 다시 입력하세요.(1~4호선) : ");
   scanf("%s", start);
   num1 = StationCode(start);
  }
  shortest_path(num1, station, Distance, NODES, found);

     printf("\n도착역 이름을 입력하세요.(1~4호선) : ");
  scanf("%s", end);
  num2 = StationCode(end);
  while(num2 == -1) {
   printf("\n도착역 이름을 다시 입력하세요.(1~4호선) : ");
   scanf("%s", end);
   num2 = StationCode(end);
  }
  fflush(stdin);

  printf("\n===============================================================================\n");

  //도착시간내 도착가능한지 판단
  if((dTime - Distance[num2]) < 0) {
   printf("\n\n\n도착시간내 도착이 불가능합니다. !! 다시 처음부터 입력해주세요.\n\n");
   getch();
   system("cls");
   continue;
  }
  // 걷는 속도 4km/h 남은시간동안 걸을 수 있는 양 검사
  walkDistance = 0.067 * (dTime - Distance[num2]);
  //printf("%lf", walkDistance);

  // 출발역 계산 함수호출
  walk = 0;
  startStation(walkDistance, num1, num2, dTime);
  shortest_path(startCode, station, Distance, NODES, found);

  //도착시간 계산
  lastHour = cHour;
  lastMin = cMin + Distance[num2] + (int)(walk/0.067);
  while( lastMin > 60 ) {
   lastHour++;
   lastMin -= 60;
  }

  // 결과값 출력
  if(num1 == startCode) {
   printf("\n\n걷기에는 시간이 부족하군요. 지하철만 타세요.\n");
   printf("\n전철 예상소요시간 = %d 분\n", Distance[num2]);
   printf("\n예상 도착 시간 = %d 시 %d 분\n\n", lastHour, lastMin);
  }
  else {
   printf("\n\n%s 역부터 %s 역까지는 도보로 이동 %.0lf 분 소요 예정\n", StationName(num1), StationName(startCode), walk/0.067);
   printf("\n전철 예상소요시간 = %d 분\n", Distance[num2]);
   printf("\n예상 도착 시간 = %d 시 %d 분\n\n", lastHour, lastMin);
  }

  shortest_path(num1, station, Distance, NODES, found);
  printf("\n최단경로 : ");
  print_path(num1, num2);
  printf("(도착)");

printf("계속 검색하시겠습니까?(Y/N) : ");
  scanf("%c", &cont);
  system("cls");
 }
}
// 출발역 지정하는 함수
void startStation(double walkDistance, int start, int end, int dTime) {
 char startStn[25];
 endSig = 0;
 if( path[end] != start)
  startStation(walkDistance, start, path[end], dTime);
 if(endSig == 1)
  return;
 walk += stationDis[path[end]][end];
 //printf("%lf ",walkDistance);
 //printf("%lf ", walk);

   // 걸을 수 있는 시간보다 거리가 늘어나면 전 역을 지정하고 리턴
 if(walkDistance < walk) {
  walk -= stationDis[path[end]][end];
  endSig = 1;
  startCode = path[end];
  return;
 }
 shortest_path(end, station, Distance, NODES, found);
 walkDistance = 0.067 * (dTime - Distance[num2]);
}