DFS/BFS 정리

학부 수업시간 이후로 오랜만에 복습했다.

 

까먹지 않게 간단명료하게 정리!

더 자세한 내용은 다음 책을 참고 바란다.

이것이 취업을 위한 코딩 테스트다 with 파이썬

DFS

Depth-First Search

말 그대로 깊이 우선 탐색이다. 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

그래프를 2가지 방식으로 표현할 수 있다.

1. 인접 행렬
   2차원 배열에 각 노드가 연결된 형태를 기록한다. 모든 관계를 저장하므로 메모리가 낭비된다는 단점이 있다.
   연결되어 있지 않은 노드끼리는 무한으로 작성한다. 실제 코드에서는 매우 큰 수로 표현.
2. 인접 리스트
   연결리스트를 이용하여 구현한다. 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
   하지만 연결된 데이터를 하나씩 확인해야 하기 때문에 특정한 두 노드가 연결되어 있는지 확인하기 위한 속도가 느리다는 단점이 있다.

DFS는 스택 자료 구조를 이용하며, 실제 구현에서는 재귀 함수를 이용했을 때 매우 간결하게 구현 가능함.

인접한 노드를 하나씩 스택 자료구조에 넣으면서 이동하다가 방문하지 않은 인접한 노드가 없을 때 스택에 있는 노드를 꺼내서 다시 탐색하는 형태이다.

---

BFS

Breadth First Search

말 그대로 너비 우선 탐색이다. 가까운 노드부터 탐색하는 알고리즘이다.

DFS는 스택 자료구조를 사용하는 것과 달리 BFS는 큐를 사용한다.

인접한 노드를 모두 큐에 넣어서 다 방문처리함과 동시에 인접한 노드를 계속해서 큐에 넣는다. 이런 식으로 가까운 노드부터 차례대로 탐색을 진행하게 되는 것.

 

from collections import deque

deque을 통해 queue = deque()으로 사용한다.