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

DFS, BFS 동시 구현

 

#pragma once

#include<map>
#include<set>
#include<string>

class C_GRAPH
{
private:
	struct S_NODE
	{
		std::string strId;
		std::set<S_NODE*> setChild;		
		bool bVisit;
	};

	std::map<std::string, S_NODE*> m_mapNode;
private:
	S_NODE* createNode(const char* strId);
	S_NODE* findNode(const char* strId);
	void searchNode(S_NODE* pNode);
public:
	C_GRAPH() = default;
	void addNode(const char* strDst, const char* strSrc);
	void print();
	void DFS(const char* strId);
	void BFS(const char* strId);
};

 

 

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

C_GRAPH::S_NODE* C_GRAPH::createNode(const char* strId)
{
	S_NODE* pNode = new S_NODE{};
	pNode->strId = strId;

	return pNode;
}

// S_NODE* == null   createNode ;
C_GRAPH::S_NODE* C_GRAPH::findNode(const char* strId)
{
	auto pairResult = m_mapNode.insert({ strId , nullptr });

	if (pairResult.second)
		pairResult.first->second = createNode(strId);

	return pairResult.first->second;
}

void C_GRAPH::addNode(const char* strDst, const char* strSrc)
{
	S_NODE* pDst = findNode(strDst);
	S_NODE* pSrc = findNode(strSrc);

	pDst->setChild.insert(pSrc);
	pSrc->setChild.insert(pDst);
}

void C_GRAPH::print()
{
	for (auto iter : m_mapNode)
	{
		printf("%s :", iter.first.c_str());
		for (S_NODE* pChild : iter.second->setChild)
		{
			printf("%s ", pChild->strId.c_str());
		}
		printf("\n");
	}
}

void C_GRAPH::searchNode(S_NODE* pNode)
{
	if (pNode->bVisit)
		return;

	pNode->bVisit = true;
	printf("%s ", pNode->strId.c_str());
	for (S_NODE* pChild : pNode->setChild)
	{
		searchNode(pChild);
	}
}


void C_GRAPH::DFS(const char* strId)
{
	printf("dfs : ");
	auto iter = m_mapNode.find(strId);
	if (iter == m_mapNode.end())
		return;

	searchNode(iter->second);
	printf("\n");
}

void C_GRAPH::BFS(const char* strId)
{
	printf("bfs : ");
	std::list<S_NODE*> que{};
	auto iter = m_mapNode.find(strId);
	if (iter == m_mapNode.end())
		return;

	S_NODE* pNode = iter->second;
	que.push_back(pNode);
	pNode->bVisit = true;

	while (!que.empty())
	{
		size_t nSize = que.size();
		for (int i = 0; i < nSize; i++)
		{
			pNode = *que.begin();
			que.pop_front();
			printf("%s ", pNode->strId.c_str());
			for (S_NODE* pChild : pNode->setChild)
			{
				if (!pChild->bVisit)
				{
					que.push_back(pChild);
					pChild->bVisit = true;
				}
			}
		}
		printf("\\");
	}
	printf("\n");

}

 

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

int main()
{
    C_GRAPH cGraph{};

    cGraph.addNode("나", "철수");
    cGraph.addNode("나", "상건");
    cGraph.addNode("나", "영미");
    cGraph.addNode("나", "영희");
    cGraph.addNode("나", "민철");
    cGraph.addNode("나", "수영");
    cGraph.addNode("나", "혜영");

    cGraph.addNode("혜영", "수영");
    cGraph.addNode("수영", "송희");
    cGraph.addNode("수영", "민철");
    cGraph.addNode("철수", "영희");
    cGraph.addNode("상건", "은미");
    cGraph.addNode("상건", "영희");
    cGraph.addNode("영희", "영미");

    cGraph.print();
    //cGraph.DFS("나");

    cGraph.BFS("수영");

    
}