DFS와 BFS(백준 1260번)

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

DFS와 BFS를 사용하는 문제이다.
우선 DFS와 BFS가 무엇인지부터 알아야 한다.

DFS란 (Depth First Search)이다
깊이를 우선적으로 탐색하는 방법이다.
서로 연결된 트리가 있다고 가정을 해보자.

위와 같은 트리가 있을때 탐색의 순서는
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
가 된다.
이렇게 탐색하는 방법에는 재귀함수를 사용하는 방법이 있다.
어떻게 하는것이냐??

간단하게 원리를 설명 하자면,
내가 어떤 노드(위의 사진에 나타난 동그라미)를 탐색했는지(방문 했는지) 확인을 할수 있는 배열을 하나 만든다
나는 check라는 이름으로 배열을 만들었다.
dfs함수에 처음으로 탐색을 시작하는 노드를 매개변수로 받아 넣어준다.
그러면 시작하는 노드가 1이라고 했을때 check[1] = true가 되는 것이다.
방문을 했다고 표시하는 것이다.(왜 방문표시를 하는가? 다시 탐색을 하지 않기 위해서이다.)
그리고 1번 노드와 연결된 다수의 노드 수 만큼 반복문을 돌려준다.
1번 노드와 연결된 다수의 노드(2, 4, 8)중 내가 방문하지 않은 노드라면 그 노드를 우선적으로 탐색한다.
그러면 2를 탐색한다. check[2]는 false이기 때문에 2번노드를 재귀함수로 처리하여 함수의 처음으로 돌아간다.

이때 헷갈리기 좋은 구조가 있다.
재귀 함수는 함수안에 함수가 실행되는 느낌이다.
예를 들면

의 형태로 되어있다.그 말은 즉 탐색이 다 끝나고 값이 반환될 때 dfs(3)이 제일 먼저 그 다음으로 dfs(2), 마지막으로 dfs(1)이 되는 구조이다.
나 또한 다른 문제에서 dfs탐색을 할때마다 횟수를 늘여주는 문제를 풀 때 count값이 계산이 잘 되지 않아 찾아보니 이러한 오류때문에 틀린 것이였다. 갑자기 생각나서 요약해봤다 참고하자!

그리고 나면 2번 노드는 자신과 연결된 노드 두개를 탐색한다. 하지만 1번 노드는 이미 지나와서 check[1] = true이다. 그러면 남은것은 3번 노드
check[3] = false이기 때문에 3번 노드를 다시 재귀로 보낸다. 이때 3번 노드는 더이상 탐색을 할 수 없기 때문에 함수의 구조는 dfs(2)로 이동하고 이 또한 더이상 탐색을 할 수 없기 때문에 dfs(1)로 이동한다 이때 1과 연결된 다른 노드를 탐색하는데 그 노드는 4번과 8번이 있다.
그러면 먼저 4번 노드로 이동하고 위의 과정을 반복해준다.
이것으로 재귀함수를 이용한 dfs를 간략히(?) 설명했다.

BFS란 (Breadth First Search)이다.
너비를 우선적으로 탐색하는 방법이다.'

아래와 같이 연결된 트리가 있다고 해보자.

이때의 탐색 순서는
1 -> 2 -> 4 -> 8 -> 3 -> 5 -> 7 -> 9 -> 6
의 순서로 된다.

BFS는 보통 Queue라는 자료구조를 사용한다.

Queue는 무엇인가?
선입 선출을 원칙으로 하고있는 자료구조이다.'
이해하기 쉽게 비유하자면
축구선수가 경기장에 들어가고 있다고 해보자.
가장 먼저 필드에 들어가는 사람이 가장 먼저 나오고 제일 마지막에 필드로 나오는 사람이 마지막에 나오는것 처럼
이렇게 먼저 들어온것이 먼저 나가는 형태의 구조를 큐라고 한다.

이번 문제에서 작동하는 큐에 대해 설명을 해 보자면
먼저 시작하는 노드의 값을 bfs함수의 매개변수로 넣어준다
그 값을 queue에 넣어준다.
넣어주고 bfs를 방문했다는 것을 표시하기 위해 check배열에 true로 표시해준다.
queue가 비어있을때까지 반복문을 진행한다. 이때 queue의 맨 앞의 값을 y라는 변수에 넣어준다.
그러고 q의 값을 꺼내고 반복문을 실행한다.
우리는 1번 노드를 우선적으로 탐색하기 때문에 1번 노드와 연결되어있는 다른 노드들은 탐색한다.
이때 연결되어있는 노드를 다 queue에 넣는다. 그리고 check행렬에 방문 표시를 해준다.
그러면 지금 queue에는 2, 4, 8이 들어있다.
그리고 다시 while문으로 올라가서 queue가 비어있는지 확인한다.
이때 queue는 비어있지 않기 때문에 queue의 맨 앞의 값인 2를 기준으로 해서 탐색을 한다.
2와 연결된 노드는 1과 3이지만 1은 이미 방문을 했기에 넘어가고 3을 방문해준다.
그러면 이때의 queue에는 4, 8, 3이 들어있다.
다시 while문의 처음으로 이동한다. 이런 방식으로 탐색을 진행하면 BFS를 다 진행하는 것이다.

코드에 대한 자세한 설명은 없다.
위의 방식을 이해하고 나면 더 이해하기 쉬울 것이다.
소스코드:

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

using namespace std;

int n, m, v;
int check[1001] = {0, };
int check_[1001] = { 0, };
vector<int> node[10001];
queue<int> q;

void dfs(int x) {
	check[x] = true;
	cout << x << " ";
	for (size_t i = 0; i < node[x].size(); i++) {
		int y = node[x][i];
		if (!check[y]) {
			dfs(y);
		}
	}
}

void bfs(int x) {
	q.push(x);
	check_[x] = true;
	while (!q.empty()) {
		int y = q.front();
		q.pop();
		cout << y << " ";
		for (long unsigned int i = 0; i < node[y].size(); i++) {
			int z = node[y][i];
			if (!check_[z]) {
				q.push(z);
				check_[z] = true;
			}
		}
	}
}

int main() {

	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		node[x].push_back(y);
		node[y].push_back(x);
	}

	for (int i = 0; i < m; i++) {
		sort(node[i].begin(), node[i].end());
	}

	dfs(v);
	cout << "\n";
	bfs(v);

}