[백준] 1260번. DFS와 BFS (C++)

문제

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

 

풀이

 

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

vector<int>DFSVisit;
void DFS(int node, const vector<vector<int>>graph)
{
	DFSVisit[node]++;
	cout << node << " ";

	for (int i = 0; i < graph[node].size(); i++)
	{
		int nextNode = graph[node][i];
		if (DFSVisit[nextNode] != 0) continue;
		DFS(nextNode, graph);
	}
}

int main() 
{
	//input////////////////////////////////////////
	int N, M, V;
	cin >> N >> M >> V;

	vector<vector<int>>graph(N+1);

	for (int i = 0; i < M; i++)
	{
		int node1, node2;
		cin >> node1 >> node2;
		graph[node1].push_back(node2);
		graph[node2].push_back(node1);
	}
	for (int i = 0; i < graph.size();i++) 
	{ sort(graph[i].begin(), graph[i].end()); }

	
	//DFS///////////////////////////////////////////
	DFSVisit = vector<int>(N + 1, 0);
	DFS(V, graph);
	cout << "\n";

	//BFS///////////////////////////////////////////
	vector<int>BFSVisit(N+1, 0);
	queue<int> q;

	q.push(V);
	BFSVisit[V]++;
	while (!q.empty())
	{
		int nowNode = q.front();
		cout<<nowNode<<" ";
		q.pop();

		for (int i = 0; i < graph[nowNode].size(); i++)
		{
			int nextNode = graph[nowNode][i];
			if (BFSVisit[nextNode] == 0) 
			{ q.push(nextNode); BFSVisit[nextNode]++;}
		}
	}
}