[C++] 5월 21일 코딩 테스트 수업

다익스트라

#pragma once

#include <iostream>
#include <map>


class C_DIJKSTRA
{
private:
	struct S_NODE
	{
		int nId;
		std::map<S_NODE*, int> child;

		bool bVisit;
		S_NODE* pParent;
		int nLength;

		bool operator()(S_NODE* Dst, S_NODE* Src)
		{
			return Dst->nLength > Src->nLength;
		}
	};

private:																																																																																			
	std::map<int, S_NODE*> m_mapNode;

private:
	S_NODE* findCreateNode(int nId);

	void printNode(S_NODE* pNode);

public:
	C_DIJKSTRA() = default;
	void add(int nDst, int nSrc, int nLenght);
	void print();

	void make(int nNode);
	void move(int nNode);
};

 

#include "Dijkstra.h"
#include <queue>

C_DIJKSTRA::S_NODE* C_DIJKSTRA::findCreateNode(int nId)
{
	auto iterResult = m_mapNode.insert({ nId, nullptr});

	if (iterResult.second)
	{
		iterResult.first->second = new S_NODE{};
		iterResult.first->second->nId = nId;
		iterResult.first->second->nLength = INT_MAX;
	}

	return iterResult.first->second;
}

void C_DIJKSTRA::add(int nDst, int nSrc, int nLenght)
{
	S_NODE* pDst = findCreateNode(nDst);
	S_NODE* pSrc = findCreateNode(nSrc);

	pDst->child.insert({ pSrc, nLenght });
	pSrc->child.insert({ pDst, nLenght });
}

void C_DIJKSTRA::print()
{
	for (auto iter : m_mapNode)
	{

		S_NODE* pNode = iter.second;

		printf("id : %d -> ", pNode->nId);

		if(pNode->pParent)
			printf("parent : %d, length : %d\n", pNode->pParent->nId, pNode->nLength);
		else
			printf("없다, length : %d\n", pNode->nLength);
	}
}

void C_DIJKSTRA::make(int nNode)
{
	std::priority_queue<S_NODE*, std::vector<S_NODE*>, S_NODE> heap{};

	S_NODE* pNode = m_mapNode.find(nNode)->second; // 부모는 null, 길이는 0이 핵심
	pNode->nLength = 0;
	heap.push(pNode);

	while (!heap.empty())
	{
		S_NODE* pParent = heap.top();
		heap.pop();

		if (!pParent->bVisit)
		{
			pParent->bVisit = true;

			for (auto pChild : pParent->child)
			{
				if (pParent->nLength + pChild.second < pChild.first->nLength)
				{
					pChild.first->pParent = pParent;
					pChild.first->nLength = pParent->nLength + pChild.second;

					heap.push(pChild.first);
				}
			}
		}

	}

}

void C_DIJKSTRA::printNode(S_NODE* pNode)
{
	if (!pNode)
		return;

	printNode(pNode->pParent);
	printf("%d ", pNode->nId);
}


void C_DIJKSTRA::move(int nNode)
{
	S_NODE* pNode = m_mapNode.find(nNode)->second;
	printNode(pNode);
}

#include <iostream>
#include "Dijkstra.h"

int main()
{
	C_DIJKSTRA cDijkstra{};
	
	cDijkstra.add(1, 2, 3);
	cDijkstra.add(1, 3, 4);

	cDijkstra.add(2, 3, 5);
	cDijkstra.add(2, 4, 10);
	cDijkstra.add(2, 6, 9);

	cDijkstra.add(3, 4, 8);
	cDijkstra.add(3, 5, 5);

	cDijkstra.add(4, 5, 6);
	cDijkstra.add(4, 6, 10);
	cDijkstra.add(4, 7, 7);
	cDijkstra.add(4, 8, 3);

	cDijkstra.add(5, 7, 4);

	cDijkstra.add(6, 8, 2);

	cDijkstra.add(7, 8, 5);

	cDijkstra.make(1);
	cDijkstra.print();
	cDijkstra.move(8);
}