[BFS, 난이도 하] 백준 1260번 DFS와 BFS

 

BFS, DFS 알고리즘의 기본 원리를 공부한 사람이라면 쉽게 풀 수 있을 만한 문제이다.

BFS(너비우선탐색)는 자신의 노드 주변에 자신이 갈 수 있는 경로들부터 탐색하는 알고리즘으로, 방문하지 않은 노드들을 모두 큐에 넣고 큐를 하나씩 빼내어 반복해내는 방법을 이용한다.

DFS(깊이우선탐색)는 자신의 노드 주변에 자신이 갈 수 있는 경로들중 하나씩을 골라서 탐색 할 수 있는 노드가 없을 까지 깊이 들어가서 탐색하는 알고리즘으로, 큐 대신 스택을 이용 할 수 있으나 재귀함수를 쓰는게 편할 수 있다.

시스템상 재귀함수도 스택의 원리이기 때문이다.

 

사진과 소스코드와 함께 문제를 풀어보자.

 

이 사진은 예제코드 2를 그린 그림이다.

우선 간선 연결 정보를 배열a 벡터에 넣어야 하는데

출력 조건중 방문할 수 있는 정점이 여러개인 경우엔 오름차 순으로 출력하라는 조건이 있다.

즉 sort 함수로 각 노드의 간선들의 연결노드를 오름차 순으로 정렬해준다.

 

특별한 조건은 이것밖에 없고 DFS, BFS는 위 설명대로 아래처럼 구현하면 문제가 해결된다. 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
bool visited[1001];
vector<int> a[1001];
void dfs(int x) {
	if (visited[x]) return;
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		dfs(y);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	queue<int> s;
	int n, m, v;
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end());
	}
	dfs(v);
	cout << '\n';
	fill(visited, visited + 1001, false);
	s.push(v);
	while (!s.empty()) {
		int t = s.front();
		s.pop();
		if (visited[t]) continue;
		visited[t] = true;
		cout << t << " ";
		for (int i = 0; i < a[t].size(); i++) {
			int y = a[t][i];
			s.push(y);
		}
	}
}