[C++] 6월 9일 코딩 테스트 수업

중간 삽입 heap

 

#pragma once

#include <stdio.h>
#include <vector>

class C_HEAP
{
public:
	struct S_NODE
	{
		int nIndex;
		int nData;
	};
private:
	std::vector<S_NODE*> m_vBuffer;
	bool (*m_pCompare)(S_NODE*&, S_NODE*&);

private:
	static bool force(S_NODE*& pDst, S_NODE*& pSrc);
	
	void addNode(S_NODE* pNode);
	void swap(int nDst, int nSrc);
	void moveUp(int nDst, bool (*pFunc)(S_NODE*&, S_NODE*&));
	void moveDown(int nDst, bool (*pFunc)(S_NODE*&, S_NODE*&));


public:
	static bool less(S_NODE*& pDst, S_NODE*& pSrc);
	static bool greater(S_NODE*& pDst, S_NODE*& pSrc);

public:
	C_HEAP() = default;
	void init(int nBufferSize = 50, bool (*pFunc)(S_NODE*&, S_NODE*&) = less);
	void add(int nData);
	void print();
	S_NODE* top();
	void pop(bool bDelete = true);
	S_NODE* getNode(int nIndex);
	void updataNode(S_NODE* pNode);
};

 

#include "heap.h"

bool C_HEAP::less(S_NODE*& pDst, S_NODE*& pSrc)
{
	return pDst->nData < pSrc->nData;
}

bool C_HEAP::greater(S_NODE*& pDst, S_NODE*& pSrc)
{
	return pDst->nData > pSrc->nData;
}

bool C_HEAP::force(S_NODE*& pDst, S_NODE*& pSrc)
{
	return true;
}


void C_HEAP::swap(int nDst, int nSrc)
{
	S_NODE* pTmp = m_vBuffer[nDst];
	m_vBuffer[nDst] = m_vBuffer[nSrc];
	m_vBuffer[nSrc] = pTmp;

	m_vBuffer[nDst]->nIndex = nDst;
	m_vBuffer[nSrc]->nIndex = nSrc;
}

void C_HEAP::moveUp(int nDst, bool (*pFunc)(S_NODE*&, S_NODE*&))
{
	int nUp = nDst / 2;
	if (nUp == 0)
		return;

	if (pFunc(m_vBuffer[nDst], m_vBuffer[nUp]))
	{
		swap(nDst, nUp);
		moveUp(nUp, pFunc);
	}
}

void C_HEAP::moveDown(int nDst, bool(*pFunc)(S_NODE*&, S_NODE*&))
{
	int nL = nDst * 2;
	int nR = nL + 1;

	if (nL >= m_vBuffer.size())
		return;

	int nSelect = nL;

	if (nR <= m_vBuffer.size() && !pFunc(m_vBuffer[nL], m_vBuffer[nR]))
		nSelect = nR;

	if (pFunc(m_vBuffer[nSelect], m_vBuffer[nDst]));
	{
		swap(nSelect, nDst);
		moveDown(nSelect, pFunc);
	}
}

void C_HEAP::init(int nBufferSize, bool (*pFunc)(S_NODE*&, S_NODE*&))
{
	m_pCompare = pFunc;
	m_vBuffer.reserve(nBufferSize);
	m_vBuffer.push_back(nullptr);
}

void C_HEAP::add(int nData)
{
	if (m_vBuffer.size() == m_vBuffer.capacity())
		return;

	S_NODE* pNode = new S_NODE{};
	pNode->nData = nData;
	addNode(pNode);
}

void C_HEAP::addNode(S_NODE* pNode)
{
	m_vBuffer.push_back(pNode);
	pNode->nIndex = (int)(m_vBuffer.size() - 1);

	moveUp((int)m_vBuffer.size() - 1, m_pCompare);
}

void C_HEAP::print()
{
	for (int i = 1; i < m_vBuffer.size(); i++)
	{
		printf("%d ", m_vBuffer[i]->nData);
	}
	printf("\n");
}

C_HEAP::S_NODE* C_HEAP::top()
{
	if (m_vBuffer.size() <= 1)
		return nullptr;

	return m_vBuffer[1];
}

void C_HEAP::pop(bool bDelete)
{
	if (m_vBuffer.size() <= 1)
		return;

	int nLast = (int)m_vBuffer.size() - 1;
	swap(nLast, 1);
	
	if(bDelete)
		delete m_vBuffer[nLast];

	m_vBuffer.pop_back();

	moveDown(1, m_pCompare);
}

C_HEAP::S_NODE* C_HEAP::getNode(int nIndex)
{
	return m_vBuffer[nIndex];
}

void C_HEAP::updataNode(S_NODE* pNode)
{
	moveUp(pNode->nIndex, force);
	pop(false);
	addNode(pNode);
}

 

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

int main()
{
	C_HEAP cHeap{};

	cHeap.init(50, C_HEAP::less);
	cHeap.add(7);
	cHeap.add(5);
	cHeap.add(8);
	cHeap.add(3);
	cHeap.add(2);
	cHeap.add(1);
	
	cHeap.print();

	C_HEAP::S_NODE* pNode = cHeap.getNode(3);
	printf("%d\n", pNode->nIndex);

	pNode->nData = 6;
	cHeap.updataNode(pNode);
	cHeap.print();
}

 

 

 

A* 알고리즘

#pragma once
#include <stdio.h>
#include "node.h"

class C_ASTAR
{
private:
	enum { E_MAX = 10 };

	int m_arMap[E_MAX][E_MAX]{};
	C_NODE m_arNode[E_MAX][E_MAX]{};


public:
	C_ASTAR();
};

 

#pragma once

class C_ASTAR;

class C_NODE
{
	friend C_ASTAR;

private:
	float F;
	float G;
	float H;
	C_NODE* pParent;
};

 

#include "astar.h"

C_ASTAR::C_ASTAR() :
	m_arNode{},
	m_arMap
	{
		{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1, 0, 0, 0, 1},
		{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
		{1, 0, 0, 1, 1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
		{1, 0, 1, 1, 1, 1, 1, 0, 0, 1},
		{1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
		{1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
	}
{
}