[알고리즘] BFS와 DFS 쉽게 이해하기

DFS는 미로찾기와 같습니다. 이미 방문한 지점을 check, flag로 표현해주고 연결된 그 다음지점부터 진행하면 됩니다.

만약 끝까지 갔는데 해당 지점이 막혀있다면, 막히지 않았던 그 전지점으로 돌아가서 시작합니다.

BFS는 처음 있는 지점에서부터 시작하는 것과 다릅니다. 처음부터 영역을 넓혀가며 하나하나 확인합니다.

 

 

 

 DFS(Depth First Search) 깊이 탐색 알고리즘에서 가장 중요한 2가지는 flag과 stack진입 조건입니다. 진입시에 flag로 먼저 판별하면 됩니다. 그리고 stack에 넣을 범위와 조건을 설정하면 됩니다.

 

int number = 7;
int flag[8];
vector<int> a[8];

void dfs(int x){
	//스택에 진입시 flag로 방문했는지 검증한다.
	if(flag[x]) return;
	flag[x] = true;
	cout << x << endl;
    
	//스택에 푸쉬할 영역을 설정한다.
	for(int i =0; i < a[x].size(); i++){

	//스택에 푸쉬할 조건을 설정한다.
	int y = a[x][i];
	dfs(y);
	}
}

int main(void) {
a[1].push_back(2);
a[1].push_back(3);

a[2].push_back(1);
a[2].push_back(3);
a[2].push_back(4);
a[2].push_back(5);

a[3].push_back(1);
a[3].push_back(2);
a[3].push_back(6);
a[3].push_back(7);

a[4].push_back(2);
a[4].push_back(5);

a[5].push_back(2);
a[5].push_back(4);

a[6].push_back(3);
a[6].push_back(7);

a[7].push_back(3);
a[7].push_back(6);

dfs(1);
return 0;
}

 

BFS는 땅따먹기와 같습니다. 특정 기준점을 중심으로 해당 영역과 관계된 부분만 먼저 탐색을 합니다. 1에서 시작했으므로, 1과 연관된 지역을 하나하나 탐색합니다.

그리고 그 다음에 영역을 하나하나 넓힙니다. 만약 DFS였다면 4지점에 3이 왔을 것입니다.

 

 

 BFS는 DFS와 다르게 Queue라는 배열로 앞으로 다가올 순서를 조정합니다. DFS은 조건에 맞으면 Depth로 깊이 한 단계씩 들어가지만, BFS는 해당 지점 기준으로 조건에 맞으면 Breadth 너비를 확장해가면서 다음 단계를 조정합니다.

 그러기 위해서 중요한 2가지가 있습니다. DFS와 마찬가지로 flag로 방문했던 지점인지 체크하고, Queue에 어떤 것을 넣을 것인지 조정하면 됩니다. DFS는 조건에 맞추어 stack에 입력했지만, BFS는 조건에 맞추어 Queue에 입력한다는 점이 다릅니다.

 

int number = 7;
int flag[7];
vector<int> a[8];

void bfs(start){
//순서에 맞춘 q를 뽑는  영역
while(!q.empty(){
int x = q.front();
q.pop();
cout << x << enld;

	// q에 넣을 범위 영역 설정
	for(int i=0; i<a[x].size(); i++){
	int y = a[x][i];
    //특정 기준에 맞추어서 q에 넣는다. 여기서는 flag가 기준이다.
	if(!flag[y]){
	q.push(y);
	flag[y] = true;
	}
	}

}



int main(void) {
a[1].push_back(2);
a[1].push_back(3);

a[2].push_back(1);
a[2].push_back(3);
a[2].push_back(4);
a[2].push_back(5);

a[3].push_back(1);
a[3].push_back(2);
a[3].push_back(6);
a[3].push_back(7);

a[4].push_back(2);
a[4].push_back(5);

a[5].push_back(2);
a[5].push_back(4);

a[6].push_back(3);
a[6].push_back(7);

a[7].push_back(3);
a[7].push_back(6);

dfs(1);
return 0;
}