BFS와 DFS, vector

https://blog.naver.com/kks227/220785731077

깊이 우선 탐색(Depth-First Search) (수정 2019-08-18)

https://blog.naver.com/kks227/220785747864

너비 우선 탐색(Breadth-First Search) (수정 2018-11-22)

https://blockdmask.tistory.com/70

[C++] vector container 정리 및 사용법

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

1260번: DFS와 BFS

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

vector<vector<int>> adj; //vector 선언
stack<int> s; //DFS를 할 때 사용함
queue<int> q; //BFS를 할 때 사용함
bool visited[1001]; //방문한 점을 확인하기 위하여 visited를 선언

void dfs(); // 함수를 선언 정의는 main함수 아래에
void bfs();

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, m, v; //정점의 개수 N(1~1000), 간선의 개수 M(1~10000), 탐색을 시작할 정점 번호
	int a, b;
	cin >> n >> m >> v;
	adj.assign(n + 1, vector<int>()); // adj를 n+1만큼 vector<int>()으로 채움
	//vector<int>(n) vector를 n만큼 0으로 채움
	for (int i = 0;i < m;i++) {
		cin >> a >> b;
		adj[a].push_back(b); //vector adj[a]에 b를 추가함
		adj[b].push_back(a); //vector adj[b]에 a를 추가함
	}
	//v[i] 정렬하기
	for (int i = 1;i <= n;i++) {
		sort(adj[i].begin(), adj[i].end()); // 오름차순
		// sort(adj[i].rbegin(), adj[i].rend()); 내림차순
	}
	visited[v] = 1; // v를 방문
	s.push(v); // stack에 v를 푸쉬
	dfs(); 
	cout << endl; // 엔터
	fill(visited, visited + n + 1, false); //visited를 0 ~ n+1 false로 채움
	visited[v] = 1;
	q.push(v); // queue에 v를 푸쉬
	bfs();
	return 0;
}


void dfs() {
	int num = s.top();
	s.pop();
	cout << num << " "; //pop할 때 출력 push할 때 해도 될 듯
	for (auto u : adj[num]) {
		if (!visited[u]) {
			s.push(u);
			visited[u] = 1;
			dfs(); //for 문 안에서 dfs() 깊게 방문함?
		}
	}
}


void bfs() {
	while(!q.empty()) {
		int num = q.front();
		q.pop();
		cout << num << " ";
		for (auto u : adj[num]) {
			if (!visited[u]) {
				q.push(u);
				visited[u] = 1;
			}
		}// for 문이 끝나고  while문 때문에 다시 bfs가 실행됨 넓게 방문함?
	}
}