코딩 공부 일기

#include "stdafx.h"

#include "DijkstraAlgorithm.h"

int main()

{

DijkstraAlgorithm dijkstra(7);    //초기화, 최대 노드수는 7

        //경로 세팅

        dijkstra.Set(0, 1, 2);    //0 -> 1 : 비용 2

        dijkstra.Set(0, 3, 5);    //0 -> 3 : 비용 5

        dijkstra.Set(1, 2, 6);

        dijkstra.Set(1, 4, 10);

        dijkstra.Set(2, 6, 3);

        dijkstra.Set(3, 4, 4);

        dijkstra.Set(3, 5, 5);

        dijkstra.Set(4, 5, 1);

        dijkstra.Set(4, 6, 7);

        dijkstra.Set(5, 6, 2);

        //최단경로 검색(0->6)

        dijkstra.FindPath(0, 6);

    return 0;

} 

#pragma once

#define INF 99999999                                               //무제한

class DijkstraAlgorithm

{

private:

        const int m_NumberOfNodes;                                 //최대 노드의 수

        int **m_Table;                                             //노드간의 거리(혹은 비용) 테이블

public:

        DijkstraAlgorithm(int NumberOfNodes);

        ~DijkstraAlgorithm();

        void Set(int From, int To, int Cost);                       //경로 세팅

        void FindPath(int From, int To);                            //경로 찾기 시작

private:

        void CalPath(int *&Path,int From);                         //경로 계산

        void PrintTable(int *cost, bool *visit, int Length);       //테이블 출력

        void PrintShortestWay(int From, int To, int *prev);        //최단 경로 출력

};

#include "stdafx.h"

#include "DijkstraAlgorithm.h"

DijkstraAlgorithm::DijkstraAlgorithm(int NumberOfNodes): m_NumberOfNodes(NumberOfNodes)

{

        //비용 테이블 초기화

        m_Table = new int*[NumberOfNodes];

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

        {

               m_Table[i] = new int[NumberOfNodes];

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

               {

                       if(i == j)

                              m_Table[i][j] = 0;

                       else

                              m_Table[i][j] = INF;

               }

        }

}

DijkstraAlgorithm::~DijkstraAlgorithm()

{

        //비용 테이블 메모리 해제

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

        {

               delete[] m_Table[i];

               m_Table[i] = NULL;

        }

        delete[] m_Table;

        m_Table = NULL;

}

//경로 세팅

void DijkstraAlgorithm::Set(int From, int To, int Cost)

{

        if (From < m_NumberOfNodes && To < m_NumberOfNodes)

        {

               m_Table[From][To] = Cost;

        }      

}

//경로 찾기 시작

void DijkstraAlgorithm::FindPath(int From, int To)

{

        //경로 저장 배열 초기화

        int *path = new int[m_NumberOfNodes];

        //경로 계산

        CalPath(path, From);

        //최단 경로 출력

        PrintShortestWay(From, To, path);

        //배열 해제

        delete[] path;

        path = NULL;

}

//경로 계산

void DijkstraAlgorithm::CalPath(int *&Path, int From)

{

        int min, index;

        int *cost = new int[m_NumberOfNodes];            //비용

        bool *visit = new bool[m_NumberOfNodes];  //방문

        //배열 초기화

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

        {

               cost[i] = INF;

               visit[i] = false;

               Path[i] = -1;

        }

        //출발위치의 비용->0으로

        cost[From] = 0;

        //총 노드의 수 만큼 반복

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

        {

               min = INF + 1;

               index = -1;

               //검색할 노드 찾기

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

               {

                       //이미 체크한 노드면 패스

                       if (visit[j])

                              continue;

                       //현재 최소값보다 더 작으면 다음 노드로

                       if (min > cost[j])

                       {

                              min = cost[j];

                              index = j;

                       }

               }

               //노드들 비용 재계산

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

               {

                       //현재 비용보다, 지금 노드에서 출발하는 비용이 더싸면 갱신

                       if (cost[j] > cost[index] + m_Table[index][j])

                       {

                              //비용 갱신

                              cost[j] = cost[index] + m_Table[index][j];

                              //경로 갱신

                              Path[j] = index;

                       }

               }

               //현재 노드는 방문한 노드로 만듬

               visit[index] = true;

               //테이블 출력(진행사항 체크용)

               PrintTable(cost, visit, m_NumberOfNodes);

        }

        delete[] cost;

        delete[] visit;

        cost = NULL;

        visit = NULL;

}

//테이블 출력

void DijkstraAlgorithm::PrintTable(int *cost, bool *visit, int Length)

{

        //번호 출력

        printf("Num\t:\t");

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

               printf("%d\t",i);

        //비용 출력

        printf("\nCost\t:\t");

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

        {

               if (cost[i] != INF)

                       printf("%d\t", cost[i]);

               else

                       printf("X\t");

        }

        //방문 여부 출력

        printf("\nVisit\t:\t");

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

               printf("%d\t", visit[i]);

        printf("\n\n");

}

//최단 경로 출력

void DijkstraAlgorithm::PrintShortestWay(int From, int To, int *prev)

{

        //출력할 경로 저장

        int *path= new int[m_NumberOfNodes];

        //저장된 경로 마지막 위치

        int lastIndex = 0;

        int final = To;         //출발 위치

        int start = From;       //도착 위치

        From = prev[To];

        //최종 도착위치 부터 역순으로 경로 추적

        while (From != start && From != -1)

        {

               path[lastIndex++] = To; 

               To = From;                            

               From = prev[From];             

        }

        //경로가 없다면

        if (From == -1)

        {

               printf("경로가 없습니다\n");

        }

        //경로가 있다면

        else

        {

               //마지막에 입력안된 노드 입력

               path[lastIndex++] = To;

               //경로 출력

               printf("최적경로 : %d -> ", start);

               for (int i = lastIndex - 1; i > 0; i--)

               {

                       printf("%d -> ", path[i]);

               }

               printf("%d\n", final);

        }

        delete[] path;

        path = NULL;

}

//환전 알고리즘

//Coins(내림차순 정렬이 되어 있어야함) : 환전 가능한 동전 배열,

//NumberOfType : 동전의 갯수, Money : 환전할 금액

void Algorithm::CoinChange(int Coins[], int NumberOfType, int Money)

{      

        int *count = new int[NumberOfType];      //환전할 각 동전의 갯수

        int type = 0;                                         //동전의 종류

        printf("환전 금액 : %d 원\n", Money);

        //환전할 각 동전 0으로 초기화

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

               count[i] = 0;

        //마지막 동전을 체크할때까지 반복

        while (type < NumberOfType)

        {

               //현재 동전이 금액보다 더 크다면 : 금액이 더 작은 동전으로 변경

               if (Coins[type] > Money)

               {

                       type++;

               }

               //현재 동전이 금액보다 작다면 : 동전 갯수를 하나 올림 & 동전의 금액만큼 돈에서 차감

               else if (Coins[type] < Money)

               {

                       Money -= Coins[type];

                       count[type]++;

               }

               //현재 돈전 = 금액 이라면 : 동전 개수 하나 올림 & 반복 종료

               else

               {

                       Money = 0;

                       count[type]++;

                       break;

               }

        }

        //각 동전 갯수 출력

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

               if(count[i] != 0)

                       printf("%d동전 %d개\n", Coins[i], count[i]);

        //환전하지 못한 금액 출력

        if(Money != 0)

               printf("환산 불가능한 금액은 %d원\n", Money);

        //동전 배열 해제

        delete count;

        count = NULL;

}