[알고리즘] 탐색알고리즘 DFS/BFS

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ

 

DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다.

 

DFS

DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다.

 

DFS의 탐색과정은 다음과 같다.

 

1. 탐색 시작 노드를 스택에 넣고, 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복한다.

DFS 예제

실행결과 : 1 2 7 6 8 3 4 5

 

---

BFS

BFS는 Breath-First Search의 약자로 너비 우선 탐색이라는 의미이다. 인접해있는 노드들을 먼저 탐색하는 알고리즘이다.

큐 자료구조를 사용하여 BFS를 구현한다.

 

BFS의 탐색 과정은 다음과 같다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS 예제

실행결과 : 1 2 3 8 7 4 5 6

 

BFS와 DFS를 배우다 보니 새로운 알고리즘을 배우는데에서 오는 즐거움을 느꼈다.