c++로 작성한 지하철 노선도 최단거리 찾기

자료구조 프로그래밍 과목을 배우면서 c++로 작성한 지하철 노선도 최단거리 찾기 프로그램입니다.(string 클래스는 사용하지 말라고 했습니다)

위와 같은 지하철 노선도가 존재할 때(a노선, b노선, c노선) 출발역과 도착역을 입력했을 경우 최단경로와 소요 시간을 출력하는 프로그램을 작성했습니다.(좌표가 같을 경우 환승(30초 소요), 같은 노선 내 이동하면 한 역당 1분 소요)

metro.h

#include <iostream>

#include <stack> //경로 위해

using namespace std;

 

#define MAX 43 //20+10+13

#define INF 9999

 

class Station

{

private:

        char line; //각 노선 구분 짓기 위해

        int num; //역 이름

        int x, y; //좌표

public:

        Station(char l='a', int n=1, int i=0, int j=0):line(l), num(n), x(i), y(j)

        {

        }

        friend class MatrixWGraph;

        friend ostream &operator<<(ostream &os, Station &s);

};

 

ostream &operator<<(ostream &os, Station &s)

{

        cout<<s.line<<s.num<<" ";

        return os;

}

 

class MatrixWGraph

{

private:

        Station metroStation[MAX]; //a, b, c 노선의 모든 역

        double length[MAX][MAX]; //간선의 길이

        double dist[MAX]; //최단 경로

        bool s[MAX]; //최단 경로 찾았는지 여부

        int path[MAX]; //시작점과 끝점 사이의 경로를 위해

public:

        MatrixWGraph()

        {

               for(int i=0; i<MAX; i++)

                       for(int j=0; j<MAX; j++)

                              if(i==j)

                                      length[i][j]=0;

                              else

                                      length[i][j]=INF;

               Initialize();

        }

        int findIndex(char line, int num)

        {

               int idx;

               int n=num;

               switch(line)

               {

               case 'a':

                       idx=num-1;

                       break;

               case 'b':

                       idx=num+19;

                       break;

               case 'c':

                       idx=num+29;

                       break;

               }

               return idx;

        }

        void AddEdge(char line1, int num1, char line2, int num2, double weight) //가중치 간선 추가

        {

               int i, j;

               i=findIndex(line1, num1);

               j=findIndex(line2, num2);

               length[i][j]=weight;

               length[j][i]=weight;

        }

        void Initialize()

        {

               //a노선

               metroStation[0]=Station('a', 1, 0, 0);

               metroStation[1]=Station('a', 2, 0, 1);

               metroStation[2]=Station('a', 3, 1, 2);

               metroStation[3]=Station('a', 4, 1, 3);

               metroStation[4]=Station('a', 5, 1, 4);

               metroStation[5]=Station('a', 6, 1, 5);

               metroStation[6]=Station('a', 7, 2, 5);

               metroStation[7]=Station('a', 8, 3, 5);

               metroStation[8]=Station('a', 9, 4, 5);

               metroStation[9]=Station('a', 10, 5, 5);

               metroStation[10]=Station('a', 11, 6, 5);

               metroStation[11]=Station('a', 12, 7, 5);

               metroStation[12]=Station('a', 13, 7, 4);

               metroStation[13]=Station('a', 14, 7, 3);

               metroStation[14]=Station('a', 15, 7, 2);

               metroStation[15]=Station('a', 16, 6, 2);

               metroStation[16]=Station('a', 17, 5, 2);

               metroStation[17]=Station('a', 18, 4, 2);

               metroStation[18]=Station('a', 19, 3, 2);

               metroStation[19]=Station('a', 20, 2, 2);

               //b노선

               metroStation[20]=Station('b', 1, 0, 5);

               metroStation[21]=Station('b', 2, 1, 4);

               metroStation[22]=Station('b', 3, 2, 4);

               metroStation[23]=Station('b', 4, 2, 3);

               metroStation[24]=Station('b', 5, 3, 2);

               metroStation[25]=Station('b', 6, 3, 1);

               metroStation[26]=Station('b', 7, 4, 1);

               metroStation[27]=Station('b', 8, 5, 1);

               metroStation[28]=Station('b', 9, 6, 1);

               metroStation[29]=Station('b', 10, 7, 1);

               //c노선

               metroStation[30]=Station('c', 1, 0, 0);

               metroStation[31]=Station('c', 2, 1, 0);

               metroStation[32]=Station('c', 3, 2, 0);

               metroStation[33]=Station('c', 4, 3, 0);

               metroStation[34]=Station('c', 5, 4, 0);

               metroStation[35]=Station('c', 6, 5, 0);

               metroStation[36]=Station('c', 7, 5, 1);

               metroStation[37]=Station('c', 8, 5, 2);

               metroStation[38]=Station('c', 9, 5, 3);

               metroStation[39]=Station('c', 10, 5, 4);

               metroStation[40]=Station('c', 11, 5, 5);

               metroStation[41]=Station('c', 12, 5, 6);

               metroStation[42]=Station('c', 13, 5, 7);

 

               //a노선 간선 추가

               AddEdge('a', 1, 'a', 2, 1);

               AddEdge('a', 2, 'a', 3, 1);

               AddEdge('a', 3, 'a', 4, 1);

               AddEdge('a', 4, 'a', 5, 1);

               AddEdge('a', 5, 'a', 6, 1);

               AddEdge('a', 6, 'a', 7, 1);

               AddEdge('a', 7, 'a', 8, 1);

               AddEdge('a', 8, 'a', 9, 1);

               AddEdge('a', 9, 'a', 10, 1);

               AddEdge('a', 10, 'a', 11, 1);

               AddEdge('a', 11, 'a', 12, 1);

               AddEdge('a', 12, 'a', 13, 1);

               AddEdge('a', 13, 'a', 14, 1);

               AddEdge('a', 14, 'a', 15, 1);

               AddEdge('a', 15, 'a', 16, 1);

               AddEdge('a', 16, 'a', 17, 1);

               AddEdge('a', 17, 'a', 18, 1);

               AddEdge('a', 18, 'a', 19, 1);

               AddEdge('a', 19, 'a', 20, 1);

               AddEdge('a', 20, 'a', 3, 1);

               //b노선 간선 추가

               AddEdge('b', 1, 'b', 2, 1);

               AddEdge('b', 2, 'b', 3, 1);

               AddEdge('b', 3, 'b', 4, 1);

               AddEdge('b', 4, 'b', 5, 1);

               AddEdge('b', 5, 'b', 6, 1);

               AddEdge('b', 6, 'b', 7, 1);

               AddEdge('b', 7, 'b', 8, 1);

               AddEdge('b', 8, 'b', 9, 1);

               AddEdge('b', 9, 'b', 10, 1);

               //c노선 간선 추가

               AddEdge('c', 1, 'c', 2, 1);

               AddEdge('c', 2, 'c', 3, 1);

               AddEdge('c', 3, 'c', 4, 1);

               AddEdge('c', 4, 'c', 5, 1);

               AddEdge('c', 5, 'c', 6, 1);

               AddEdge('c', 6, 'c', 7, 1);

               AddEdge('c', 7, 'c', 8, 1);

               AddEdge('c', 8, 'c', 9, 1);

               AddEdge('c', 9, 'c', 10, 1);

               AddEdge('c', 10, 'c', 11, 1);

               AddEdge('c', 11, 'c', 12, 1);

               AddEdge('c', 12, 'c', 13, 1);

               //환승역 소요시간 추가

               AddEdge('a', 1, 'c', 1, 0.5);

               AddEdge('a', 5, 'b', 2, 0.5);

               AddEdge('a', 10, 'c', 11, 0.5);

               AddEdge('a', 17, 'c', 8, 0.5);

               AddEdge('a', 19, 'b', 5, 0.5);

               AddEdge('b', 8, 'c', 7, 0.5);

        }

        int Choose(int n) //s[w]가 0이고 dist[u]가 dist[w] 중 최소일 때 반환

        {

               int min=INF;

               int u=-1; //정점이 음수일 수는 없으므로 초기값을 -1

               for(int w=0; w<n; w++)

                       if(!s[w]&&dist[w]<min)

                       {

                              min=dist[w];

                              u=w;

                       }

               return u;

        }

        void ShortestPath(const int n, const int v)

        {

               //dist[j], 0<=j<n은 n개의 정점을 가진 방향 그래프 G에서

               //정점 v에서 정점 j까지의 최단 경로 길이로 설정됨

               //간선의 길이는 length[i][j]로 주어짐

               for(int i=0; i<n; i++)

               {

                       s[i]=false;

                       path[i]=-1;

                       dist[i]=length[v][i];

               }

               s[v]=true;

               dist[v]=0;

               for(int i=0; i<n-2; i++) //정점 v로부터 n-1개 경로를 결정

               {

                       int u=Choose(n); //s[w]가 0이고 dist[u]가 dist[w] 중 최소일 때 반환

                       s[u]=true;

                       for(int w=0; w<n; w++)

                              if(!s[w]&&dist[u]+length[u][w]<dist[w])

                              {

                                      path[w]=u; //바뀌기 전에 저장

                                      dist[w]=dist[u]+length[u][w];

                              }

               }

        }

        void result(char line1, int num1, char line2, int num2)

        {

               int i, j, idx;

               stack<int> s;

               i=findIndex(line1, num1);

               j=findIndex(line2, num2);

               ShortestPath(MAX, i);

               idx=j; //도착역이 바뀌면 안되므로

               cout<<metroStation[i].line<<metroStation[i].num<<" -> ";

               while(1) //도착역 직전역부터 출발역 다음역까지 stack에 넣고

               {

                       if(path[idx]==-1)

                              break;

                       s.push(path[idx]);

                       idx=path[idx];

               }

               while(!s.empty()) //스택이 빌때까지 출력하면 순서가 맞다

               {

                       int v=s.top();

                       s.pop();

                       cout<<metroStation[v].line<<metroStation[v].num<<" -> ";

               }

               cout<<metroStation[j].line<<metroStation[j].num<<endl;

               double time=dist[j];

               double second=time-(int)time;

               cout<<"소요시간 : "<<(int)time<<"분 ";

               if(second)

                       cout<<"30초"<<endl;

               else

                       cout<<endl;

        }

};

 

hw10.cpp

#include "hw10.h"

 

int main(void)

{

        MatrixWGraph g;

        char s1[4], s2[4];

        char line1, line2;

        int num1, num2;

        cout<<"출발역 : ";

        cin>>s1;

        cout<<"도착역 : ";

        cin>>s2;

        cout<<"============================================"<<endl;

        line1=s1[0];

        if(!s1[2])

               num1=(int)(s1[1]-48);

        else

               num1=(int)((s1[1]-48)*10+(s1[2]-48));

        line2=s2[0];

        if(!s2[2])

               num2=(int)(s2[1]-48);

        else

               num2=(int)((s2[1]-48)*10+(s2[2]-48));

        g.result(line1, num1, line2, num2);

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~