BFS&DFS

DFS & BFS 개념과 구현

---

탐색 알고리즘과 자료구조, 직관적으로 이해하기

---

DFS, BFS 등의 용어는 컴퓨터공학 계열 전공자 또는 개발 관련 공부를 진행해본 사람들이라면 한 번씩은 모두들 들어보았을 것이다.

들어보긴 들어봤으나, 그 개념과 구현은 생각보다 쉽지만은 않다.

이들을 탐색할 때 쓰이는 트리와 스택 또는 큐와 같은 자료구조까지 알아야 할 것들이 너무 많기도 할 뿐더러 이러한 알고리즘을 처음 접할때는 왜 stack queue등이 필요한지 잘 와닿지 않는다.

이것부터 알아보도록 하자!

자료구조가 왜 필요해?

---

한 예시를 들어보자.

어떠한 게임을 진행하면서 가능한 모든 경우의 수들을 생각해보고, 그 이후의 경우의 수도 모두 확인해보고자 할 때

우리는 기억에 용이함을 위하여 메모지에 메모 또는 머리속에 저장 등의 방법을 이용한다.

우리가 직접 탐색을 할 때는 스택/큐 등의 자료구조를 쓰지는 않았지만 메모지, 머리 등과 같은 매개를 이용하여 저장을 해두었다.

어떠한 상태를 저장해 두어야, 그 다음의 상태를 확인하고 계속 탐색을 진행할 수 있기 때문이다.

예를 들어, 현재 상황에서 시도해 볼 수 있는 선택 가지수가 총 10가지일 때, 나머지 9가지는 잠시 미뤄두고

한 가지에 대해서 그 다음 단계를 앞서 생각해 본다면, 나머지 9가지는 어떻게 해야할까?

어딘가에 잘 기록하고 저장해두어야 지금 탐색한 선택지가 틀렸을 때 다시 돌아와서 다른 선택지를 다시 탐색해볼 수 있다.

이와 같이, 잠시 저장 해 두는 과정은 프로그래밍으로 구현하는 알고리즘에서도 필수불가결한 요소이기 때문에 스택

또는 큐 라는 자료구조를 이용하여 선택지들을 담아둔다.

스택과 큐, 둘이 어떻게 다른가

---

우리는 DFS(Depth First Search) 를 진행할 때 스택을 , BFS(Breath First Search)를 진행할 때 큐를

필요로 한다. 둘 다 모두 자료를 저장한다는 관점에서는 같지만 자료를 사용하는 순서가 다르다!

스택의 경우, LIFO방식을 채택하고 있다.

Last In First Out은 이름 그대로 후입선출을 의미한다.

반면, 큐는 '줄을 서서 기다리는 것'이라는 의미로, 줄에 합류한 순서 그대로 줄을 빠져나가는 것이다.

FIFO방식을 채택하고 있다.

그래서 First In First Out으로써 선입선출을 의미한다.

이와 같이 자료를 저장하는 관점에서는 같은 용도이지만 다른 사용방식을 가진 스택과 큐를 탐색하면서 적절히 활용해 필요한 것들을 잠시 저장해 두거나, 필요시 다시 빼서 사용할 수 있다.

이제 탐색을 위한 준비요소를 모두 공부해보았으니, 이는 코드로 어떻게 구현 되는지, 그리고 DFS와 BFS에서는 스택과 큐를 사용해야 하는지 등을 확인해보자

깊이우선탐색(DFS), 너비우선탐색(BFS) 구현하기

---

탐색 알고리즘과 그에 쓰이는 자료구조들을 알아보았으니 이제 BFS, DFS 알고리즘의 기본적 형태를 구현해보자.

이는 기본적인 형태를 잡는 과정으로 이를 바탕으로 응용하여 문제에 적용시킬수 있다.

DFS는 한 단게에서 pop과 expand 두가지 일을 동시에 처리한다.

• pop은 스택의 최상위 노드를 꺼내는 작업을 말한다.
• expand는 pop을 통해 노드를 지우면서 그 노드의 인접한, 자식 노드들을 스택에 넣는 작업을 말한다.
  만일 자식이 존재하지 않는다면 아무것도 넣지 않는다.

DFS

---

def DFS(graph, root):
   stack = [root]                    # stack에 root 노드 삽입
   visited = []                    # 방문노드 확인을 위한 배열
   while stack:                    # 스택이 끝날때 까지 반복
       n = stack.pop()                # 스택 최상단 노드 pop
       for i in graph[n]:            # 최상단 노드의 인접노드 순차 방문
           if i not in visited:    
               stack.append(i)        # 방문 배열에 없을 경우, 추가
           if n not in visited:
               visited.append(n)    # 방문 배열에 없을 경우, 추가
           print('v', visited)    
       return visited

BFS

---

def BFS(graph, root):
   queue = [root]                    # queue에 root
   visited = []                    # 방문노드 확인을 위한 배열
   while queue:                    # 큐가 끝날때 까지 반복
       n = queue.pop(0)            # 제일 먼저 들어온 원소 pop
       if n not in visited:        
           visited.append(n)        # 방문 배열에 없을 경우 추가
       for i in graph[n]:
           if i not in visited:        
               queue.append(i)        # 방문 배열에 없을 경우 추가
       return visited