[BAEKJOON] 1260번 : DFS와 BFS

문 제

 

소 스  코 드

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>

typedef std::map<int, std::set<int>> Graph;
typedef std::vector<int> Answer;

void DFS(Graph&, const int&, bool *, const int&);
void BFS(Graph&, const int&, bool *, const int&);

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

	int N, M, V;

	std::cin >> N >> M >> V;

	bool *num{ new bool[N + 1] };

	Graph nodes;

	int firstDot, secondDot;
	for (int i = 0; i < M; ++i) {
		std::cin >> firstDot >> secondDot;

		nodes[firstDot].insert(secondDot);
		nodes[secondDot].insert(firstDot);
	}

	// DFS, start dot : V
	DFS(nodes, V, num, N);

	// BFS
	BFS(nodes, V, num, N);

	delete[] num;
}

void DFS(Graph& g, const int& start, bool * arr, const int& N) {
	std::fill_n(arr, N + 1, false);
	Answer answer;
	answer.reserve(g.size());

	std::stack<int> st;
	
	st.push(start);
	arr[start] = true;
	answer.emplace_back(start);
	

	while (!st.empty()) {
		int index{ st.top() };
		for (auto iter = g[index].begin(); ; ++iter) {
			if (g[index].end() == iter) {
				st.pop();
				break;
			}
			if (false == arr[(*iter)]) {
				st.push(*iter);
				arr[*iter] = true;
				answer.emplace_back(*iter);
				break;
			}
		}
	}

	for (const auto& a : answer) std::cout << a << " ";
	std::cout << '\n';

	return;
}


void BFS(Graph& g, const int& start, bool * arr, const int& N) {
	std::fill_n(arr, N + 1, false);
	Answer answer;
	std::queue<int> logs;

	answer.reserve(g.size());

	arr[start] = true;
	answer.emplace_back(start);
	
	logs.push(start);

	while (!logs.empty()) {
		int index{ logs.front() };
		logs.pop();
		
		for (const auto& a : g[index]) {
			if (false == arr[a]) {
				logs.push(a);
				answer.emplace_back(a);
				arr[a] = true;
			}
		}

	}

	for (const auto& a : answer) std::cout << a << " ";
	std::cout << '\n';


	return;
}

 

풀 이

 

BFS란, Breadth First Search 의 약자로 너비를 우선으로 탐색합니다.
DFS란, Depth First Search 의 약자로 깊이를 우선으로 탐색합니다.

만약, A ~ D의 정점이 존재하고, 5개의 간선이 존재한다고 합니다.

이 그래프는 시작이 A라는 가정하에, 오른쪽과 같이 표현 할 수 있다.

이 때, 

1층은 A

2층은 C, D

3층은 E, B

 

BFS를 할 경우, 너비 우선 탐색 이기 때문에, A -> C -> D -> E -> B 순으로 탐색이 됩니다.

DFS의 경우, 깊이 우선 탐색 이기 때문에, A -> C -> E -> D -> B 순으로 진행 됩니다.

 

만약 이 그래프에 하나의 노드가 더 있다고 할 때, 

BFS와 DFS의 진행 순서는

BFS, A -> C -> D -> ? -> E -> B

DFS, A -> C -> ? -> E -> D -> B

 

구현을 할 경우, 

BFS : A -> C -> D -> ? -> E -> B

DFS : A -> C -> ? -> C -> E -> C -> A -> D -> B

순으로 진행한다고 생각을 하여,

BFS의 경우에는 STL queue를 사용하였고,

DFS의 경우에는 STL stack을 사용하여 구현을 하였습니다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/1260

1260번: DFS와 BFS