BFS

BFS정의

너비 우선 검색(BFS)은 주어진 속성을 충족하는 노드의 트리 데이터 구조를 검색하는 알고리즘입니다.

시작 노드에서 시작하여 다음 깊이 수준의 노드로 이동하기 전에 현재 깊이의 모든 노드를 탐색합니다. 추가 메모리로 queue를 사용하며 아직 탐색하지 않은 하위 노드를 추적하는 데 필요합니다.

시작점(시작 노드)의 인접한 정점들을 차례로 방문하고, 방문했던 정점을 시작으로 해서 다시 인접한 노드들을 차례로 방문해서 트리의 모든 노드를 너비 우선으로 탐색한다.

그래프 실습

그래프 예시

그래프 탐색과정 BFS

BFS기본 코드

그래프 : G = { V, E }
정점들의 집합 : V
간선들의 집합 : E
어디로 이동할 수 있는지 : Adj[ ]
잠시 다음으로 이동할 수 있는 노드를 임시로 넣어두는 저장소 : Q(queue형태)
방문했던 노드인지 확인하는 저장소 : visited(list형태로 bool값 이용) 방문하지 않은 경우 : F
방문한 경우 : T

pseudocode

S에서 시작
S as visited
Q에 push(S)
while ( !Q.empty() )
	S = Q top/pop
    for ( i in adj[S] )
    	if ( ! visited[i] )
        	Q에 push(i)
            visited[i] = true

c++ code

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

//코드 시작
//n_vertices : 정점의 개수
//*visited : 각 정점의 방문 여부(bool타입 사용)
//adj: 각 정점이 어떤 정점들과 연결 되어있는지(vector구현, list사용)
//dist: 정감간 얼마나 떨어져 있는지 거리 (vector구현)

class CGraph {
	int n_vertices;
	bool* visited;
	vector<list<int>> adj; //간선
	vector<int> dist; //정점간 얼마나 떨어져 있는지

public:
	CGraph(int _n) { //생성자
		this->n_vertices = _n;
		visited = new bool[_n];
		for (int i = 0; i < _n; ++i) { //초기화(방문하지 않음)
			visited[i] = false;
		}
		adj.resize(_n); //adj vector -> 주어진 개수만큼 만듬
		dist.resize(_n); //거리 vector -> 주어진 개수만큼 만듬
	}
	~CGraph() {
		delete visited; //멤버 변수 visited는 포인터 변수임으로 소멸자에서 삭제한다.
	}

	//방향이 없을 때
	void addUndirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
		adj[_d].push_back(_s);
	}
	//방향을 넣어주고 싶을때
	void addDirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
	}

	//하나의 정점에서 시작하는 경우
	void BFS(int _s) {
		visited[_s] = true;		// 시작점_s 방문
		queue<int> Q;			// 추가메모리를 큐의 형태로 만듬 
		Q.push(_s);				// 시작점 _s를 큐에 넣음 
		while (!Q.empty()) {	// 큐에 더이상 정점이 남아있지 않을 때까지 반복
								// 큐는 FIFO형태로 먼저 들어간 것이 먼저 나온다. 		
			_s = Q.front();		// 큐에 가장 먼저 들어간 정점의 값을 꺼낸다.
			Q.pop();			// 그리고 꺼낸 큐의 정점은 큐에서 삭제합니다.
											//이터레이터 사용(포인터와 유사)
											// 연결된 정점은 리스트로 연결되어 iterator를 이용해 탐색
			list<int>::iterator iter;		// 큐에서 꺼낸 정점(_s)과 연결되어 있는 정점들(adj[_s])을 차례로 탐색
			for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter) { // iterator를 사용하는 방법
				if (!visited[*iter]) {			// 방문하지 않은 정점만 탐색
					visited[*iter] = true;		// _s 근처의 *iter 정점 중 방문하지 않은 경우 방문한다. 
					Q.push(*iter);				// 그리고 방문한 근처 정점 *iter를 큐에 넣는다.
				}
			}
		}
	}


	//여러 정점에서 시작하는 경우
	void BFS(vector<int> _docks) {

		//시작노드2개 추가부분
		int n_docks = _docks.size();
		queue<int> Q;
		for (int i = 0; i < n_docks; ++i) {
			visited[_docks[i]] = true; //시작점으로 모두 방문한 뒤에
			Q.push(_docks[i]); //시장점을 큐에 넣어주면 된다.
		}

		int _s = 0;
		while (!Q.empty()) {
			//STL에서는 pop의 형태 사용 불가
			_s = Q.front(); //빼낼 값을 보는 것과 삭제하는 것을 따로 구현
			Q.pop();
			//이터레이터 사용(포인터와 유사)
			list<int>::iterator iter; //같은 컨테이너에 저장되어 있는 원소를 참조
			for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter){//모든 원소를 본다.
				if (!visited[*iter]) { //방문하지 않은 정점만 탐색한다.
					Q.push(*iter); //방문한 근처 정점* iter를 큐에 넣는다.
					visited[*iter] = true; //_s 근처의 *iter 정점 중 방문하지 않은 경우 방문한다.
				}
			}
		}
		for (int i = 0; i < n_vertices; ++i) {		// 저장한 거리들을 확인해 봅니다. 콘솔창에 간략히 출력할게요.
			cout << i << " : " << dist[i] << endl;
		}
	}
};

int main() {
	CGraph OGraph(10);				
	OGraph.addUndirectedEdge(0, 1);	
	OGraph.addUndirectedEdge(0, 2);
	OGraph.addUndirectedEdge(1, 3);
	OGraph.addUndirectedEdge(1, 4);
	OGraph.addUndirectedEdge(2, 3);
	OGraph.addUndirectedEdge(3, 4);
	OGraph.addUndirectedEdge(4, 5);
	OGraph.addUndirectedEdge(4, 6);
	OGraph.addUndirectedEdge(4, 7);
	OGraph.addUndirectedEdge(5, 7);
	OGraph.addUndirectedEdge(5, 8);
	OGraph.addUndirectedEdge(5, 9);
	OGraph.addUndirectedEdge(6, 7);
	OGraph.addUndirectedEdge(7, 8);
	return 0;
}

iterator

• 반복자 이터레이터는 포인터와 유사하다.
• vector, deque, set, map, list등과 같은 컨테이너에 저장되어 있는 원소를 참조(접근)할 떄 사용된다.
• stack, queue에는 iterator가 없다.
• 선언

vector<int>::iterator i;
list<string>::iterator i;
deque<int>::iterator i;

BFS문제

연습문제1

문제소개

수거 로봇을 이용해 쓰레기를 수거한다.
쓰레기 로봇이 충전할 수 있는 정착장이 있다.
쓰레기와 쓰레기, 정착장과 쓰레기 거리는 모두 1KM로 동일하다.
각 쓰레기가 정착장과 얼마나 떨어져 있는지 구하여라

문제풀이

해당 문제의 그래프를 간단하게
v={0,1,2,3,4,5,6,7,8,9}
E={{0,1},{0,2},{1,2},{1,3},{1,4},{2,3},{3,4},{4,5},{4,6},{4,7},{5,7},{5,8},{5,9},{6,7},{7,8}}
로 나타낼 수 있다.
시작점을 기준으로 다른 각 노드들과의 거리를 구하는 문제이다. BFS 방법을 이용해서 문제를 해결할 수 있다.

• 시작점의 인근에 위치하는 노드들을 먼저 탐색한 후 해당 거리에 거리를 추가로 더하면서 쉽게 풀 수 있다.
• 정점간의 떨어진 거리를 나타내는 코드를 추가한다.

vector<int> dist;

• 각 정점간의 떨어진 거리는 모두 1KM로 동일하다.

dist[*iter] = dist[_s] + 1; 

• 출력코드를 추가해 준다.

for (int i = 0; i < n_vertices; ++i) {		
			cout << i << " : " << dist[i] << endl;
		}

위의 코드들을 BFS알고리즘에 추가하여 문제를 풀어보자!

문제코드

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

class CGraph {
	int n_vertices;
	bool* visited;
	vector<list<int>> adj; 
	vector<int> dist; //정점간 얼마나 떨어져 있는지

public:
	CGraph(int _n) {
		this->n_vertices = _n;
		visited = new bool[_n];
		for (int i = 0; i < _n; ++i){
			visited[i] = false;
		}
		adj.resize(_n);
		dist.resize(_n);
	}
	~CGraph() {
		delete visited;
	}

	//방향이 없을 때
	void addUndirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
		adj[_d].push_back(_s);
	}
	//방향을 넣어주고 싶을때
	void addEDirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
	}

	//BFS 알고리즘
	void BFS(int _s) {
		visited[_s] = true;		// 시작점이니 _s는 당연히 방문했습니다. 
		queue<int> Q;			// 큐를 만들어 정점을 탐색하기 위한 준비를 합니다. 
		Q.push(_s);				// 우선 시작점 _s를 큐에 넣어줍니다. 
		
		int _s = 0;
		while (!Q.empty()) {
			_s = Q.front(); //stl에서는 pop사용 불가해서
			Q.pop(); //보는 얘랑 삭제하는 애랑 따로 구현
			list<int>::iterator iter; //저장된 값을 본다.
			for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter)//이터레이터 사용, 모든 원소를 본다.
				if (!visited[*iter]) //포인터로 표현해주어야 한다.
					Q.push(*iter);
			visited[*iter] = true;
			dist[*iter] = dist[_s] + 1; //거리 +1 적용추가
		}
        for (int i = 0; i < n_vertices; ++i) {		
			cout << i << " : " << dist[i] << endl;
		}
	}
};

int main() {
	CGraph OGraph(10);
	OGraph.addUndirectedEdge(0, 1);
	OGraph.addUndirectedEdge(0, 2);
	OGraph.addUndirectedEdge(1, 2);
	OGraph.addUndirectedEdge(1, 3);
	OGraph.addUndirectedEdge(1, 4);
	OGraph.addUndirectedEdge(2, 3);
	OGraph.addUndirectedEdge(3, 4);
	OGraph.addUndirectedEdge(4, 5);
	OGraph.addUndirectedEdge(4, 6);
	OGraph.addUndirectedEdge(4, 7);
	OGraph.addUndirectedEdge(5, 7);
	OGraph.addUndirectedEdge(5, 8);
	OGraph.addUndirectedEdge(5, 9);
	OGraph.addUndirectedEdge(6, 7);
	OGraph.addUndirectedEdge(7, 8);

	OGraph.BFS(3); //시작점 3

	return 0;
}

연습문제2

문제소개

수거 로봇을 이용해 쓰레기를 수거한다.
쓰레기 로봇이 충전할 수 있는 정착장이 2개 이상 존재한다.
쓰레기와 쓰레기, 정착장과 쓰레기 거리는 모두 1KM로 동일하다.
각 쓰레기가 가장 가까운 정착장과 얼마나 떨어져 있는지 구하여라

문제풀이

해당 문제의 그래프를 간단하게
v={0,1,2,3,4,5,6,7,8,9}
E={{0,1},{0,2},{1,2},{1,3},{1,4},{2,3},{3,4},{4,5},{4,6},{4,7},{5,7},{5,8},{5,9},{6,7},{7,8}}
로 나타낼 수 있다.
시작점을 기준으로 다른 각 노드들과의 거리를 구하는 문제이다. BFS 방법을 이용해서 문제를 해결할 수 있다. 연습문제1에서 사용한 정점간의 떨어진 거리를 이용하는 코드를 그대로 유지하며, 추가로 시작노드를 2개 이상이 되도록 코드를 추가 또는 수정한다.

• 시작점을 2개 이상 받아야 하기 때문에 파라미터를 동적으로 나타낼 수 있는 vector를 사용한다. 노드들은 정수로 표현되어 있어 int형으로 가져온다.

vector<int> _docks

• vector는 동적이기 때문에 시작점의 개수를 변수에 넣어 확인해주는 과정이 필요하다.

int n_docks = _docks.size();

• 모든 정점을 방문한 뒤에 시작점을 큐에 넣어주면 큐의 성질을 이용해서 2개 이상의 시작점을 표현할 수 있다.

for (int i = 0; i < n_docks; ++i) {
			visited[_docks[i]] = true;
			Q.push(_docks[i]); 
		}

위의 코드들을 BFS알고리즘에 추가하여 문제를 풀어보자!

문제코드

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

class CGraph {
	int n_vertices;
	bool* visited;
	vector<list<int>> adj; 
	vector<int> dist; 

public:
	CGraph(int _n) {
		this->n_vertices = _n;
		visited = new bool[_n];
		for (int i = 0; i < _n; ++i){
			visited[i] = false;
		}
		adj.resize(_n);
		dist.resize(_n);
	}
	~CGraph() {
		delete visited;
	}

	//방향이 없을 때
	void addUndirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
		adj[_d].push_back(_s);
	}
	//방향을 넣어주고 싶을때
	void addEDirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
	}

	//BFS 알고리즘
	void BFS(vector<int> _docks) {
		int n_docks = _docks.size();	
		queue<int> Q;
		for (int i = 0; i < n_docks; ++i) {
			visited[_docks[i]] = true;	
			Q.push(_docks[i]);			
		}
		int _s = 0;
		while (!Q.empty()) {			
			_s = Q.front();
			Q.pop();
			list<int>::iterator iter;
			for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter) {
				if (!visited[*iter]) {
					visited[*iter] = true;
					Q.push(*iter);
					dist[*iter] = dist[_s] + 1;
				}
			}
		}
		for (int i = 0; i < n_vertices; ++i) {		
			cout << i << " : " << dist[i] << endl;
		}
	}
};

int main() {
	CGraph OGraph(10);
	OGraph.addUndirectedEdge(0, 1);
	OGraph.addUndirectedEdge(0, 2);
	OGraph.addUndirectedEdge(1, 2);
	OGraph.addUndirectedEdge(1, 3);
	OGraph.addUndirectedEdge(1, 4);
	OGraph.addUndirectedEdge(2, 3);
	OGraph.addUndirectedEdge(3, 4);
	OGraph.addUndirectedEdge(4, 5);
	OGraph.addUndirectedEdge(4, 6);
	OGraph.addUndirectedEdge(4, 7);
	OGraph.addUndirectedEdge(5, 7);
	OGraph.addUndirectedEdge(5, 8);
	OGraph.addUndirectedEdge(5, 9);
	OGraph.addUndirectedEdge(6, 7);
	OGraph.addUndirectedEdge(7, 8);
	vector docks = { 0, 3 }; //시작점 0, 3
	OGraph.BFS(docks);		
	return 0;

}

DFS

하단의 주소를 눌러서 DFS(+ BFS와 DFS의 차이점/DFS문제)를 확인할 수 있습니다.
https://velog.io/@ehekaanldk/DFS