[BOJ] 1260: DFS와 BFS / C++

개요

DFS와 BFS 연습했습니다.

이론만 계속 알고 있었고, 빡구현은 안했었기 때문에 풀기로 하였습니다.

풀러가기

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

코드

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

class Graph
{
public:
	Graph( int _nodeCount )
	{
		infoVectors = new vector<int>[_nodeCount + 1];

		nodeCount = _nodeCount;
	}

	void AddLine( int n1, int n2 )
	{
		infoVectors[n1].push_back(n2);
		infoVectors[n2].push_back(n1);
	
		sort(infoVectors[n1].begin(), infoVectors[n1].end());
		sort(infoVectors[n2].begin(), infoVectors[n2].end());
	}

	vector<int>* GetInfoVector()
	{
		return infoVectors;
	}

	int GetNodeCount()
	{
		return nodeCount;
	}

private:
	vector<int>* infoVectors;
	int nodeCount;
};

class BFS
{
	public:
		BFS(Graph _graph)
		{
			graph = &_graph;
			infoVectors = _graph.GetInfoVector();

			nodeCount = graph->GetNodeCount();

			visitNode = new bool[nodeCount + 1];

			for (int i = 0; i < nodeCount + 1; ++i)
			{
				visitNode[i] = false;
			}
		}

		int* Find(int startNode, int& size)
		{
			find = {};

			FindStack(startNode);

			int visitSize = find.size();

			int* visitArray = new int[visitSize];
			size = visitSize;

			for (int i = 0; i < visitSize; ++i)
			{
				if (!find.empty())
				{
					visitArray[i] = find.front();
					find.pop();
				}
				else
					break;
			}

			return visitArray;
		}

		void FindStack(int node)
		{
			 queue<int> targetQueue;

			 visitNode[node] = true;
			 find.push(node);
			 targetQueue.push(node);

			 while (!targetQueue.empty())
			 {
				 int front = targetQueue.front();
				 int lineCount = infoVectors[front].size();

				 for (int i = 0; i < lineCount; ++i)
				 {
					 if (visitNode[infoVectors[front][i]] == false)
					 {
						 find.push(infoVectors[front][i]);
						 targetQueue.push(infoVectors[front][i]);

						 visitNode[infoVectors[front][i]] = true;
					 }
				 }

				 targetQueue.pop();
			 }
		}

	private:
		Graph* graph;
		vector<int>* infoVectors;
		queue<int> find;
		bool* visitNode;

		int nodeCount;
};

class DFS
{
public:
	DFS(Graph _graph)
	{
		graph = &_graph;
		infoVectors = _graph.GetInfoVector();

		nodeCount = graph->GetNodeCount();

		visitNode = new bool[nodeCount + 1];

		for (int i = 0; i < nodeCount + 1; ++i)
		{
			visitNode[i] = false;
		}
	}

	int* Find( int startNode, int &size )
	{
		find = {};

		FindStack(startNode);

		int visitSize = find.size();

		int* visitArray = new int[visitSize];
		size = visitSize;

		for (int i = 0; i < visitSize; ++i)
		{
			if (!find.empty())
			{
				visitArray[i] = find.front();
				find.pop();
			}
			else
				break;
		}

		return visitArray;
	}

	void FindStack(int node)
	{
		find.push(node);
		visitNode[node] = true;
		int size = infoVectors[node].size();

		while (true)
		{
			int minNode = -1;

			for (int i = 0; i < size; ++i)
			{
				if (visitNode[infoVectors[node][i]] == false)
				{
					if (minNode == -1)
						minNode = infoVectors[node][i];
					else if (minNode > infoVectors[node][i])
						minNode = infoVectors[node][i];
				}
			}

			if (minNode != -1)
				FindStack(minNode);
			else
				break;
		}
	}

private:
	Graph* graph;
	vector<int>* infoVectors;
	queue<int> find;
	bool* visitNode;

	int nodeCount;
};

int main()
{
	int nodeCount;
	int lineCount;
	int startIndex;

	int node1;
	int node2;

	cin >> nodeCount >> lineCount >> startIndex;

	Graph graph(nodeCount);

	for (int i = 0; i < lineCount; ++i)
	{
		cin >> node1 >> node2;

		graph.AddLine(node1, node2);
	}

	DFS dfs(graph);

	int resultSize = 0;
	int* dfsResult = dfs.Find(startIndex, resultSize);

	for (int i = 0; i < resultSize; ++i)
		cout << dfsResult[i] << " ";

	cout << endl;

	BFS bFS(graph);

	int* bfsResult = bFS.Find(startIndex, resultSize);

	for (int i = 0; i < resultSize; ++i)
		cout << bfsResult[i] << " ";

	cout << endl;

	return 0;
}