[백준] 1260 DFS와 BFS

문제출처] https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

문제요약

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

DFS와 BFS

1. DFS(Depth-First Search), 깊이 우선 탐색

DFS의 구현은 스택을 이용하여 한다. 명시적으로 스택을 이용하여 구현할 수도 있지만 일반적으로 재귀 호출을 통하여 구현을 많이한다. 재귀 호출 과정에서 스택 자료구조가 이용되므로 자연스러운 것이다. 

소스코드는 C/C++로 작성되었습니다. 

vector<int> a[1001];
int d[1001];

void dfs(int start) {
	if (d[start]) return;
	d[start] = true;
	cout << start << ' ';
	for (int i = 0; i < a[start].size(); i++) {
		int y = a[start][i];
		dfs(y);
	}
}

시작 노드를 시작으로 그래프를 재귀적으로 순회하면서 탐색을 한다.

2. BFS(Breadth-First Search), 너비 우선 탐색

BFS는 큐를 이용하여 구현할 수 있다. BFS는 "맹목적인 탐색"을 하고자 할 때 주로 이용된다. 또, 최단경로를 찾아준다는 점에서 최단 길이를 보장할 때 사용된다. 

BFS 알고리즘은 다음의 순서를 따른다.

1. 큐에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드에 방문하고, 차례대로 큐에 삽입힌다.
3. 1,2 번 과정을 큐가 빌 때까지 반복한다. 

소스코드는 C/C++로 작성되었습니다. 

vector<int> a[1001];
int b[1001];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	b[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << ' ';
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (!b[y]) {
				q.push(y);
				b[y] = true;
			}
		}
	}
}

큐를 선언해주고 큐에 데이터를 삽입하고 방출하는 과정을 반복한다.

풀이

이 문제는 DFS와 BFS를 구현하는 문제이다. 단, 데이터를 나열할때 오름차순으로 나열해야하므로 sort함수를 이용하여 정렬해준 뒤 함수를 실행시키면 된다.

---

소스코드는 C/C++로 작성되었습니다.

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

using namespace std;

vector<int> a[1001];
int b[1001];
int d[1001];

bool compare(int a, int b) {
	return a < b;
}

void bfs(int start) {
	queue<int> q;
	q.push(start);
	b[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << ' ';
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (!b[y]) {
				q.push(y);
				b[y] = true;
			}
		}
	}
}

void dfs(int start) {
	if (d[start]) return;
	d[start] = true;
	cout << start << ' ';
	for (int i = 0; i < a[start].size(); i++) {
		int y = a[start][i];
		dfs(y);
	}
}

int main() {
	int n, m, start;
	cin >> n >> m >> start;
	for (int i = 1; i <= m; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		a[v1].push_back(v2);
		a[v2].push_back(v1);
	}

	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end(), compare);
	}
	dfs(start);
	cout << '\n';

	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end());
	}
	bfs(start);
}