[C++] 4월 30일 코딩 테스트 수업

#pragma once

#include <iostream>
#include <set>
#include <list>

class C_MOUNTAIN
{
public:
	enum class E_TYPE
	{
		E_PATH = 0,
		E_GATE,
		E_SUMMIT,
	};
private:
	struct S_NODE
	{
		std::set<int> child;
		E_TYPE eType;
	};
	S_NODE** m_arNode;
	int** m_arIntentsity{};
	std::set<int> m_setEnalbeNode;
	std::list<int> m_listPath;

private:
	S_NODE* createNode(int nId);
	void move(int nParent, int nId, int nIntensity);

public:
	C_MOUNTAIN() = default;
	void addPath(int nDst, int nSrc, int nIntensity);
	void init(int nSize);
	void setType(int nId, E_TYPE eType);
	void print();
	void run(int nGate);
};

 

#include "mountain.h"

C_MOUNTAIN::S_NODE* C_MOUNTAIN::createNode(int nId)
{
	S_NODE* pNode = new S_NODE{};
	pNode->eType = C_MOUNTAIN::E_TYPE::E_PATH;

	return pNode;
}


void C_MOUNTAIN::run(int nGate)
{
	move(0, nGate, 0);

}

void C_MOUNTAIN::move(int nParent, int nId, int nIntensity)
{
	/*printf("id : %d , intensity : %d\n", nId, m_arIntentsity[nId][nParent]);*/

	S_NODE* pNode = m_arNode[nId];
	if (pNode->eType == E_TYPE::E_SUMMIT)
	{
		for (int nPath : m_listPath)
		{
			printf("%d ", nPath);
		}
		printf("result : %d\n", nIntensity);
		return;
	}

	for (int nChild : pNode->child)
	{
		S_NODE* pChild = m_arNode[nChild];
		if (nChild != nParent && pChild->eType != E_TYPE::E_GATE)
		{
			m_listPath.push_back(nChild);
			if (nIntensity < m_arIntentsity[nId][nChild])
				move(nId, nChild, m_arIntentsity[nId][nChild]);
			else
				move(nId, nChild, nIntensity);

			m_listPath.pop_back();
		}
	}
}

void C_MOUNTAIN::init(int nSize)
{
	m_arNode = new S_NODE * [nSize] {};
	m_arIntentsity = new int* [nSize] {};
	for (int i = 0; i < nSize; i++)
	{
		m_arIntentsity[i] = new int[nSize] {};
	}
}

void C_MOUNTAIN::addPath(int nDst, int nSrc, int nIntensity)
{
	if (!m_arNode[nDst])
		m_arNode[nDst] = createNode(nDst);
	if (!m_arNode[nSrc])
		m_arNode[nSrc] = createNode(nSrc);

	m_setEnalbeNode.insert(nDst);
	m_setEnalbeNode.insert(nSrc);

	m_arNode[nDst]->child.insert(nSrc);
	m_arNode[nSrc]->child.insert(nDst);

	m_arIntentsity[nDst][nSrc] = nIntensity;
	m_arIntentsity[nSrc][nDst] = nIntensity;
}


void C_MOUNTAIN::setType(int nId, E_TYPE eType)
{
	m_arNode[nId]->eType = eType;
}

void C_MOUNTAIN::print()
{
	for (int nId : m_setEnalbeNode)
	{
		printf("%d : ", nId);
		for (int nChild : m_arNode[nId]->child)
		{
			printf("%d ", nChild);
		}
		printf("\n");
	}
}

 

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

int main()
{
    C_MOUNTAIN cMountain{};

    cMountain.init(10);

    cMountain.addPath(1, 2, 3);
    cMountain.addPath(2, 3, 5);
    cMountain.addPath(2, 4, 2);
    cMountain.addPath(2, 5, 4);
    cMountain.addPath(3, 4, 4);
    cMountain.addPath(4, 5, 3);
    cMountain.addPath(4, 6, 1);
    cMountain.addPath(5, 6, 1);

    cMountain.setType(1, C_MOUNTAIN::E_TYPE::E_GATE);
    cMountain.setType(3, C_MOUNTAIN::E_TYPE::E_GATE);
    cMountain.setType(5, C_MOUNTAIN::E_TYPE::E_SUMMIT);

    //cMountain.print();
    cMountain.run(3);


}