DFS(Depth First Search)와 BFS(Breath First Search)

• 깊이 우선 탐색(Depth First Search)
  • 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
  • 재귀함수를 기반으로 순환 알고리즘의 형태를 지님.
    
• 너비 우선 탐색(Breath First Search)
  • 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
  • 재귀함수로 동작하지 않는다.
  • 큐를 사용하여 효율적으로 구현 가능하다.

미로찾기에서도 사용된다.
https://codepen.io/Owlree/details/PPomzo

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int ans[1001][1001];
int v[1001];
queue<int> q;

void dfs(int s) {
	cout << s << " ";
	v[s] = 1;
	for(int i = 1; i <= n; i++) {
		if(v[i] == 1 || ans[s][i] == 0) continue;
		dfs(i);
	}
}

void bfs(int s) {
	q.push(s);
	v[s] = 0;

	while(!q.empty()) {
		s = q.front();
		cout << s << " ";
		q.pop();
		for(int i = 1; i <= n; i++) {
			if(ans[s][i] == 0 || v[i] == 0) continue;
			q.push(i);
			v[i] = 0;
		}
	}
}

int main() {
	int a, b, s;
	cin >> n >> m >> s;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		ans[a][b] = ans[b][a] = 1;
	}
	dfs(s);
	cout << endl;
	bfs(s);
}

위 코드는 1260번 내 채점 소스코드를 복붙해왔다.
https://www.acmicpc.net/problem/1260