DFS/BFS 알고리즘

!!개인 공부용이기 때문에 틀린 내용이 있을 수도 있습니다!! 잘못된 내용이 있으면 언제든지 지적해 주세요.

DFS와 BFS 알고리즘
이름 그대로 깊이 우선으로 탐색하는 것이 DFS, 너비우선으로 탐색하는 것이 BFS 알고리즘이다.
코딩테스트 단골문제이므로 잘 알아놓는 것이 좋다

DFS

이미지 출처: 위키피디아

사진의 숫자는 방문하는 순서이다.
보다시피 한 노드에서 옆의 형제 노드들을 탐색하지 않고 자식 노드를 우선 탐색한다. 더 이상 자식 노드가 없을 때까지 탐색한 후 형제 노드를 탐색하고 이 과정을 반복하며 모든 노드를 탐색하는 방식이 깊이 우선 탐색이다. 이름처럼 제일 깊은 노드까지 탐색한 후 그 옆의 노드를 탐색하는 방식이다.
나같은 경우는 DFS를 구현할 때 이런 방식을 주로 사용한다.

/*
start	시작 노드 
n	노드의 개수
visit	방문 여부를 저장하는 bool 배열
arr	노드간에 간선이 존재하는지를 표시(1인 경우 간선 존재)
*/
void DFS(int start){
	visit[start] = true;
    for(int i=0; i<n; i++){
    	if(arr[start][i] == 1 && !visit[i])
        	DFS(i);
	}
}

BFS

이미지 출처: 위키피디아

사진의 숫자는 방문하는 순서이다.
BFS는 DFS와는 반대로 형제 노드들을 먼저 방문한다.
형제 노드들을 모두 탐색한 후에 자식 노드를 탐색하는 것을 반복하며 모든 노드를 탐색하는 방식이 BFS 방식이다. 코드로 구현할 때는 현재 노드와 연결된 모든 노드들을 큐를 사용해서 담아놓고 하나씩 pop해가며 탐색하는 방식을 사용한다.

/*
start	시작 노드
n	노드의 개수
visit	방문여부를 저장하는 bool 배열
arr	간선 존재 여부(1이면 간선 존재)
queue	현재 노드에 연결된 모든 노드들을 담아줄 큐
*/
void BFS(int start){
	queue<int> q;
    q.push(start);
    visit[start] = true;
    
    while(!q.empty()){
    	int tmp = q.front();
        q.pop();
        for(int i=0; i<n; i++){
        	if(arr[start][i] == 1 && !visit[i]){
            	q.push(i);
                visit[i] = true
            }
        }
    }
}