DFS/BFS 탐색 알고리즘

• DFS 알고리즘의 개념

DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

그래프는 노드와 간선으로 표현된다.

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.

• DFS 알고리즘의 특징

특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후,

다시 돌아가 다른 경로로 탐색하는 알고리즘

 

 

• DFS 알고리즘의 순서

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

---

위의 예제가 가장 흔한 예제로, visited라는 배열 리스트를 두고, 이를 이용해 해당 노드를 방문했는지를 체크한다. 이 때

graph에는 각 노드마다 인접한 노드들이 리스트 형태로 저장되어 있다. 따라서 이를 재귀적으로 방문하게 되면, 스택에 삽입된 순서대로 출력되게 된다.

 

이 예시에서는 v에 1을 넣었으므로 먼저 1이 출력된다

 

그리고 graph의 index 1에는 2,3,8이 인접 행렬로 주어져 있다. 그러면 이 순서대로 노드들을 방문하게 되고, 이것이 재귀적으로 반복되게 된다. 이와 같은 방법을 쓰게 되면, 인접한 행렬을 우선적으로 방문하되 인접한 행렬 중에서 가장 작은 수부터 방문하게 되는 조건이 완성되게 된다.

 

여기서 확장하게 되면, 2차원 배열로, 방향과 관련된 알고리즘 문제가 출제되게 되는데 이 때 dfs를 요긴하게 활용할 수 있다. 방향에 따라서 동,서,남,북 4방향이 있기 때문에 위처럼 재귀함수를 4번 처리해주면 된다.

---

 

• BFS의 개념

너비 우선 탐색이라는 의미를 가지며, 가까운 노드부터 탐색하는 알고리즘이다.

선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.

 

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

---

 

위에서 언급한 대로 큐 자료구조를 사용하여 알고리즘을 구현하면 된다. 이 떄, deque을 import 하여 사용하기도 하는데 이는 배열이 1차원 배열일 때는 이대로 사용하는 게 좋지만 2차원 배열 이상일 때는 deque을 사용하기 어려워진다 .이 때는 import하여 deque을 사용하기 보다는 2차원 배열 이상으로 나타내고 del을 이용하여 popleft()를 구현하는 것이 좋다.

 

해당 코드를 분석해보자면 graph에서 dfs와 처음에는 동일하게 1에 대한 방문처리를 해주고, 그 뒤에는 그 다음번 순번의 노드들을 queue에 append하게 되고, 해당 값들을 pop할 때마다 그에 해당하는 index의 graph에서 append를 해준다. 이를 통해 너비 우선적으로 확장해나가는 것을 알 수 있다.

 

이 코드는 bfs 문제 중에 난이도가 있는 문제를 푼 것이다. 이를 보면 위에서 언급한 내용대로 2차원 배열 이상의 queue 구조에서는 deque을 import 하여 활용하기보다는 이처럼 queue에 넣고 첫번째 리스트를 del함으로써 pop 을 구현하는 것을 알 수 있다. 

 

• 정리

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용