[백준/BOJ] 백준 1260번 : DFS와 BFS

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

1260번: DFS와 BFS

그래프를 생성한 뒤 방문할 수 있는 정점이 여러개 일때 정점의 번호가 작은 것부터 방문하므로, 각 정점에 연결된 정점들을 오름차순으로 정렬한다.

 

코드

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

vector<vector<int>> adj;
vector<bool> visited;
vector<bool> discoverd;
int n, m;
int v;

//dfs를 실행한다
void solveDfs(int here)
{
	//here위치를 방문했다고 표시한다
	visited[here] = true;

	//방문한 위치 출력
	cout << here << " ";

	//정점의 번호가 작은것 부터 방문한다
	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		//방문하지 않은곳이라면 방문한다
		if (!visited[there])
		{
			solveDfs(there);
		}
	}
}

//bfs를 실행한다
void solveBfs(int start)
{
	//시작 위치를 큐에 넣는다
	queue<int> q;
	q.push(start);

	//시작위치를 발견되었다고 표시한다
	discoverd[start] = true;

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

		//현재 탐색하는 위치를 출력한다
		cout << here << " ";

		//해당 위치에 인접한 정점들을 발견한다
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			//발견된적 없던 곳이라면
			if (!discoverd[there])
			{
				//발견되었다고 표시하고
				discoverd[there] = true;

				//나중에 탐색할것이므로 큐에 넣는다
				q.push(there);
			}
		}

	}

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp1, temp2;

	cin >> n >> m >> v;

	adj = vector<vector<int>> (n+1);
	visited = vector<bool>(n + 1, false);
	discoverd = vector<bool>(n + 1, false);

	//그래프를 생성한다
	for (int i = 0; i < m; i++)
	{
		cin >> temp1 >> temp2;
		adj[temp1].push_back(temp2);
		adj[temp2].push_back(temp1);
	}

	//방문할 수 있는 정점이 여러개인경우 정점의 번호가 작은것 먼저 방문하므로
	//연결된 정점들을 오름차순으로 정렬한다
	for (int i = 1; i <= n; i++)
	{
		sort(adj[i].begin(), adj[i].end());
	}

	solveDfs(v);
	cout << "\n";

	solveBfs(v);

	return 0;
}