[백준 1260 : DFS와 BFS] - C++

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int VerNumber = 0;
int LineNumber = 0;
int StartNumber = 0;
int CheckArr[10001];
vector<int> node[1001];

void BFS() {
	queue<int> q;
	q.push(StartNumber);
	int target = 0;
	int index = 1;

	while (!q.empty())
	{
		target = q.front();
		q.pop();

		int nodeSize = node[target].size();

		
		cout << target << " ";
		for (int i = 0; i < nodeSize; i++)
		{
			int NextTarget = node[target][i];
			if ( CheckArr[NextTarget] == 0)
			{
				CheckArr[NextTarget] = 1;				
				q.push(NextTarget);
			}
		}
	}
	cout << "\n";
}

void DFS(int p )
{
	cout << p << " ";
	CheckArr[p] = 1;
	int nodesize = node[p].size();
	for (int i = 0; i < nodesize; i++)
	{
		int cur = node[p][i];
		if (CheckArr[cur] == 0)
		{
			DFS(cur);
		}
	}

}

int main() {
	cin >> VerNumber >> LineNumber >> StartNumber;
	int input1 = 0;
	int input2 = 0;

	for (int i = 0; i < LineNumber; i++)
	{
		cin >> input1 >> input2;
		node[input1].push_back(input2);
		node[input2].push_back(input1);

		sort(node[input1].begin(), node[input1].end());
		sort(node[input2].begin(), node[input2].end());
	}

	//DFS
	CheckArr[StartNumber] = 1;
	DFS(StartNumber);
	cout << "\n";


	//clear
	for (int i = 0; i < 10000; i++) {
		CheckArr[i] = 0;
	}

	//BFS
	CheckArr[StartNumber] = 1;	
	BFS();

	return 0;
}