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

#pragma once

#include <iostream>
#include <queue>

class C_KRUSKAL
{
private:
	struct S_NODE
	{
		char c1;
		char c2;
		int nLength;

		bool operator()(S_NODE s1, S_NODE s2) const 
		{
			return s1.nLength > s2.nLength;
		}
	};

private:
	int m_arNode[127][127];
	std::priority_queue<S_NODE, std::vector<S_NODE>, S_NODE> m_heap;

public:
	C_KRUSKAL() = default;
	void add(char cDst, char cSrc, int nLenght);
	void print();
	void run();
};

 

#include "kruskal.h"
#include <list>

void C_KRUSKAL::add(char cDst, char cSrc, int nLenght)
{
	m_arNode[cDst][cSrc] = nLenght;
	m_arNode[cSrc][cDst] = nLenght;

	if(cDst < cSrc)
		m_heap.push({ cDst, cSrc, nLenght });
	else
		m_heap.push({ cSrc, cDst, nLenght });
}

void C_KRUSKAL::print()
{
	for (char c1 = 'A'; c1 <= 'I'; c1++)
	{
		for (char c2 = 'A'; c2 <= 'I'; c2++)
		{
			printf("%2d ", m_arNode[c1][c2]);
		}
		printf("\n");
	}
}

void C_KRUSKAL::run()
{
	char arParent[127]{};
	for (int i = 0; i < 127; i++)
	{
		arParent[i] = i;
	}

	std::list<S_NODE> listResult{};

	while (!m_heap.empty())
	{
		S_NODE node = m_heap.top();
		m_heap.pop();
	
		// 둘이 부모가 같으면 패스
		// 둘이 부모가 다를경우 작은 부모로 둘다 교체 
		// 결과에 추가 
		if (arParent[node.c1] != arParent[node.c2])
		{
			char cParent = arParent[node.c1];

			if (cParent > arParent[node.c2])
				cParent = arParent[node.c2];

			arParent[node.c1] = cParent;
			arParent[node.c2] = cParent;

			// 과제 : 이거 버그가 있는게 c -> b를 연결할때 H의 부모도 A로 바뀌어야하는데 안됨 , 힌트는 포인터

			listResult.push_back(node);
		}
	}
}

 

#include <iostream>

#include "kruskal.h"

int main()
{
	C_KRUSKAL cKruskal{};

	cKruskal.add('A', 'B', 3);
	cKruskal.add('A', 'I', 7);
	cKruskal.add('B', 'C', 5);
	cKruskal.add('B', 'I', 6);

	cKruskal.add('C', 'H', 4);
	cKruskal.add('C', 'G', 6);
	cKruskal.add('C', 'F', 8);
	cKruskal.add('C', 'D', 9);

	cKruskal.add('D', 'F', 12);
	cKruskal.add('D', 'E', 9);
	cKruskal.add('E', 'F', 10);
	cKruskal.add('F', 'G', 2);

	cKruskal.add('G', 'I', 11);
	cKruskal.add('H', 'I', 7);

	//cKruskal.print();
	cKruskal.run();
}