[백준] 알고리즘 1260번 - DFS와 BFS문제

문제

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

1260번: DFS와 BFS

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
using namespace std;
int n, m, v;
vector<int> g[1001];
bool check[1001];
queue<int> qu;
void dfs(int index) {
	check[index] = true;
	cout << index << " ";
	for (int i = 0; i < g[index].size(); i++) {
		int next = g[index][i];
		if (check[next]) continue;
		check[next] = true;
		dfs(next);
	}
	return;
}
void bfs(int index) {
	memset(check, false, sizeof(check));
	check[index] = true;
	qu.push(index);
	while (!qu.empty()) {
		int node = qu.front();
		qu.pop();
		cout << node << " ";
		for (int i = 0; i < g[node].size(); i++) {
			int next = g[node][i];
			if (check[next]) continue;
			check[next] = true;
			qu.push(next);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++) sort(g[i].begin(), g[i].end());
	dfs(v);
	cout << "\n";
	bfs(v);
}

해설

그래프 탐색의 목적 - 한 정점에서 시작해서 연결된 모든 정점을 한 번씩 방문하는 목적이다.

방문 순서에 따라 DFS,BFS로 나뉜다.

인접리스트의 검사하는 순서가 문제에서 작은 순으로 방문하라고 되어있기에 정렬해줍니다.

DFS는 깊게 탐색하기 때문에 처음 시작정점 1에서 시작하면 1->2->4->3 순으로 방문하게됩니다.

BFS는 넓이 우선 탐색이기에 처음 시작정점에 복제본을 파견시킨다고 보면됩니다. 그럼 1에 연결된 정점들은 2,3,4가 있기에 1,2,3,4를 출력하게 되는 것입니다.

자세한건 소스코드를 확인하면서 DFS와 BFS의 틀을 배우시는게 좋습니다.