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

크루스칼 알고리즘

#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:
	char m_arParent[127]{};
	int m_arNode[127][127];
	std::priority_queue<S_NODE, std::vector<S_NODE>, S_NODE> m_heap;
	char findParent(char c);
	void setParent(char c, char cParent);

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");
	}
}

char C_KRUSKAL::findParent(char c)
{
	if (m_arParent[c] == c)
		return c;

	return findParent(m_arParent[c]);
}

void C_KRUSKAL::setParent(char c, char cParent)
{
	if (c != m_arParent[c])
		setParent(m_arParent[c], cParent);

	m_arParent[c] = cParent;
}


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

	std::list<S_NODE> listResult{};

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

		if (cParent1 != cParent2)
		{
			char cNewParent = cParent1;

			if (cNewParent > cParent2)
				cNewParent = cParent2;

			setParent(node.c1, cNewParent);
			setParent(node.c2, cNewParent);

			listResult.push_back(node);
		}
	}

	for (S_NODE node : listResult)
	{
		printf("%c, %c, %d\n", node.c1, node.c2, node.nLength);
	}
}

#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();
}

 

 

 

양, 늑대, 양배추, 농부 문제

비트 마스크를 사용해서 할것이기에 사전 문제 확인

#include <iostream>

enum class E_TYPE
{
    E_NULL = 0,
    E_CABBAGE  = 0x01,
    E_SHEEP = 0x02,
    E_WOLF = 0x04,
    E_FAMER = 0x08,
};

void print(int nType);

int main()
{
    int nType = (int)E_TYPE::E_CABBAGE | (int)E_TYPE::E_FAMER | (int)E_TYPE::E_SHEEP;
    print(nType);

    // 주의해야할 점 -> 내가 얼마만큼 뒤집어줘야하는지 작업을 거쳐서 사용해야함 (부호까지 전부 뒤집어버림), 0000 1101 -> 1111 0010 이런식으로 값이 나와서 잘못된 값이 나오게 된다.
    //int nAnother = ~nType;
    //print(nAnother);

	int nAnother = ~nType & 15; // 즉, 전부 뒤집은 다음에 내가 쓰고싶은만큼의 범주만 선택해서 잘라서 사용해야함 / and를 씌워서 뺴온 것 
	print(nAnother);
}

void print(int nType)
{
    if (nType & (int)E_TYPE::E_CABBAGE)
        printf("양배추 ");
    if (nType & (int)E_TYPE::E_SHEEP)
        printf("양 ");
    if (nType & (int)E_TYPE::E_WOLF)
        printf("늑대 ");
    if (nType & (int)E_TYPE::E_FAMER)
        printf("농부 ");
    printf("\n");
}