[알고리즘] DFS와 BFS

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

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

입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

main함수

• 입력될수있는 정점의 최대개수는 1000개이므로 크기가 1001인 벡터를 선언한다. 그리고 방문체크배열 check도 선언한다.
• 연결된 간선을 입력받을 때
  a[u].push_back(v);
  a[v].push_back(u);
  이런 식으로 해주는데 왜냐하면 a의 각 요소가 노드라고 생각하고 그 노드에 어떤 값들이 연결되어있는지 저장해야하기 때문이다. (vector에 저런식으로 자식값?을 추가할수있는게 신기하다..)
  => 인접리스트를 만들어줌
• 방문해야하는 정점번호가 작은것부터 방문해라고 하니 a배열의 각 요소가 가진값들을 오름차순으로 정렬해준다.
• bfs와 dfs를 실행해준다

DFS

깊이 우선 탐색(DFS, Depth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다

그럼 dfs함수를 보면 시작노드인 node를 인수로 받는다. 그리고 node는 시작하는 값이라서 방문체크배열인 check의 node번째에 방문했다는 표시로 true를 넣는다. 그리고는 node와 연결된 다른 노드들을 for문을 통해서 한다.
dfs를 구현하는 방식은 재귀함수를 사용하거나 스택을 사용할수있는데, 아래의 방식은 재귀함수를 호출해서 풀었음

시간복잡도를 생각해보면,
인접리스트를 구현해서 풀었기때문에 O(정점의 수+간선의 수)의 시간복잡도를 가진다(인접행렬로 풀면 시간복잡도가 달라짐)

BFS

너비 우선 탐색(BFS, Breadth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

BFS는 재귀적으로 동작하지 않는다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
즉, 선입선출(FIFO) 원칙으로 탐색한다.

시간복잡도를 보면,
인접리스트를 만들어서 풀었기때문에 dfs와 같이 O(정점의 수+간선의 수)의 시간복잡도를 가진다(인접행렬로 풀면 시간복잡도가 달라짐)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <stdio.h>

using namespace std;

vector < int > a[1001];
bool check[1001];

void dfs(int node) {
	check[node] = true;
	cout << node << " ";
	for (int i = 0; i < a[node].size(); i++) {
		int next = a[node][i];
		if (!check[next]) { // next번째 노드가 이미 방문된 곳이라면 if문안의 재귀함수가 실행되지 않는다
			dfs(next); // 재귀함수가 작동하게되면 next가 dfs함수의 node가 되어 실행된다
		}
	}
}


void bfs(int start) {
	queue<int> q; // 시작노드부터 시작해서 while문을 통해 반복하면서 인접한 노드를 q에 담는다.
	bool bfsCheck[1001] = { false, }; // 방문체크배열

	bfsCheck[start] = true;
	q.push(start);
	while (!q.empty()) {
		int node = q.front();
		q.pop(); // 이미 방문한 노드는 q에서 제거해준다 > 제거해주지 않으면 무한루프에 빠지게된다.
		cout << node << " ";
		for (int i = 0; i < a[node].size(); i++) {
			int next = a[node][i];
			if (!bfsCheck[next]) {
				bfsCheck[next] = true; // 방문했으면 꼭 true를 넣어줘야한다.
				q.push(next);
			}
		}
	}
}

int main(void) {
	int n, m, start;
	scanf("%d %d %d", &n, &m, &start);

	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		a[u].push_back(v);
		a[v].push_back(u);
	}

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

	dfs(start);
	puts("");
	bfs(start);
	puts("");
	return 0;

}