[BOJ]1260번: DFS와 BFS(c++)

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

1260번: DFS와 BFS

 

 

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

using namespace std;

// 너비 우선 탐색
void bfs(vector<vector<int>>& list, vector<bool>& visited, int start)
{
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty())
	{
		int q_node = q.front();
		cout << q_node << ' ';
		
		q.pop();

		for (int i = 0; i < list[q_node].size(); ++i)
		{
			if (!visited[list[q_node][i]])
			{
				visited[list[q_node][i]] = true;
				q.push(list[q_node][i]);
			}
		}
	}

}

// 깊이 우선 탐색
void dfs(vector<vector<int>> &list, vector<bool> &visited, int start)
{
	cout << start << ' ';
	visited[start] = true;

	for (int i = 0; i < list[start].size(); ++i)
	{
		if (!visited[list[start][i]])
		{
			dfs(list, visited, list[start][i]);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int node, edge, start;
	cin >> node >> edge >> start;

	// 인접 리스트 생성
	vector<vector<int>> list(node + 1);
	{
		int n1, n2;
		for (int i = 0; i < edge; ++i)
		{
			cin >> n1 >> n2;

			list[n1].push_back(n2);
			list[n2].push_back(n1);
		}
	}

	// 오름차순 정렬
	for (int i = 1; i <= node; ++i)
	{
		sort(list[i].begin(), list[i].end());
	}

	// dfs 출력
	vector<bool> visited(node + 1);
	dfs(list, visited, start);
	cout << '\n';

	// bfs 출력
	fill(visited.begin(), visited.end(), 0);
	bfs(list, visited, start);

	return 0;
}

 

이제야 bfs/dfs가 좀 이해간다..

둘의 차이점을 자세히 설명한 사이트 : https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

 

이걸 초월 번역을 좀 해서 정리해보자면 다음과 같다. 

	BFS( Breadth First Search )  너비우선 탐색	DFS ( Depth First Search ) 깊이 우선 탐색
구현 방식	Queue큐 구조를 사용해서 최소 거리를 찾는다.	Stack스택 구조를 사용한다.
	ㄱ. 큐에 저장된 노드를 한번에 하나씩 pop하며 체크한다. ㄴ. 해당 노드의 인접 노드들을 큐에 push한다.	ㄱ. 방문한 노드를 스택에 push한다. ㄴ. 해당 노드의 인접 노드가 없으면 스택의 노드를 pop한다.
공통점	가능한 모든 노드를 탐색한다. 따라서 둘다 시간 복잡도가 O(V + E)이다.  ( V = 노드, E = 간선 )
차이점1	DFS보다 느리다	BFS보다 빠르다
2	가중치 없는 그래프에서, 한 노드에서 시작했을 때의 최소 경로로 탐색한다. BFS는 시작 노드에서 "최소개수의 간선"으로 노드를 탐색하기 때문이다.	시작 노드에서 목적 노드까지 BFS보다 좀 더 많은 간선을 지난다.
3	시작 노드에서 가까운 노드를 탐색할 때 적합하다.	시작 노드에서 멀리 떨어진 노드를 탐색할때 적합하다.
4	BFS는 의사결정 트리를 만드는데에 적합하지 않다. 이웃한 노드 탐색이 우선이기 때문이다.	DFS는 게임이나 퍼즐에서 의사결정 트리를 만드는데에 적합하다. 1. 의사결정 후, 2. 모든 경우의 수를 다 따져보기 때문에, 이기는 케이스를 만나게 되면 stop할 수 있다.

(원본 링크와 표 순서가 다르며, 초급자의 이해를 우선으로 번역했습니다)

 

 

bfs/dfs는 서로 목적이 다르다.

 

가능한 모든 노드를 탐색하는 것은 둘다 같다.

하지만 bfs의 목적은 "최소개수의 간선"으로 모든 노드를 탐색하는 것이고

dfs의 목적은 그냥 모든 노드를 탐색하는 것이다. 이때 거의 모든 간선을 돌아다니게 된다. 

 

문제에서 적합한 방식을 선택할 때에는 이것을 기준으로 하자.