BFS, DFS 알고리즘

코테 문제들을 많이 풀다보면 난이도가 중급(?)이상부터 자주 등장하는 알고리즘이었다. 자주 사용되길래 어떤 알고리즘인지 공부해야되겠다 싶었다.

---

BFS(Breath Frist Search) - 넓이 우선탐색

bfs는 넓이 우선 탐색으로 다음 깊이(Depth)로 넘어가기 전에 해당 층에 있는 노드들을 먼저 전부 탐색하는 것이다. 그래서 탐색의 순서는 선입선출이다. 탐색 대기열에 추가된 순서대로 탐색을 진행한다.

 

DFS(Depth Frist Search) - 깊이 우선 탐색

dfs는 깊이 우선 탐색으로 다음 넓이(Breath)로 넘어가기 전에 해당 줄기에서 연결된 노드들을 끝까지 먼저 탐색한 후에 남아 있는 같은 층 노드를 탐색하는 방법이다. 그래서 이 순서는 후입선출이다. 탐색 대기열에 마지막으로 추가된 노드부터 탐색을 진행한다.

진행 방향 :
----------------------------->
        -   C 
A - B 
        -   D   -   F   -   H
                -   G  
        -   E
        
bfs - 선입선출, queue를 활용한 알고리즘. A->B->C->D->E->F->G->H
dfs - 후입선출, stack을 활용한 알고리즘. A->B->C->D->F->H->G->E

탐색의 시작점은 A다. 우선 bfs 알고리즘을 통한 탐색을 순서대로 들여다 보면

 

1. 대기열에 A에서 갈 수 있는 B를 추가하게 된다.

2. A와 같은 방법으로 탐색 대기열에는 [C,D,E]가 추가된다. B탐색이 끝났으므로  선입된 C탐색을 시작한다.

3. C에서 더이상 갈 수 있는 노드가 없으므로 탐색 대기열은 [D,E]. 다음 선입된 D 탐색을 시작한다.

4. D에서 갈 수 있는 노드는 F,G가 있으므로 탐색 대기열에 추가해주면 [E,F,G]가 된다. 다음 선입인 E 탐색을 시작한다.

 

이와 같은 과정을 H까지 반복하게 된다. 여기서 각 노드들은 양방향 이동이 가능하기 때문에 탐색을 진행했는지 확인해줘야한다.

그래서 visit이라는 배열을 만들어 탐색한 노드라면 넘어가고 탐색하지 않은 노드라면 해당 노드에서 갈 수 있는 노드 목록을 대기열에 추가해준다. 그렇게 되면 visit에 자연스럽게 탐색 순서에 맞춰서 노드들이 저장된다.

 

dfs알고리즘은 위 순서에서 선입된 노드를 탐색하는게 아닌 후입된 노드들부터 탐색을 하면 된다.

 

그래서 이 과정을 코드로 구현을 하면 아래와 같다.

def bfs(arr, start):
    queue = list()
    visit = list()

    queue.append(start)

    while queue:
        # print(f'qu : {queue} \t\t\t visit : {visit}')
        node = queue.pop(0)
        print(f'node : {node}')
        if node not in visit:
            visit.append(node)
            queue.extend(arr[node])

def dfs(arr, start):
    stack = list()
    visit = list()

    stack.append(start)

    while stack:
        print(f'stack : {stack} \t\t\t visit : {visit}')
        node = stack.pop()
        print(f'node : {node}')
        if node not in visit:
            visit.append(node)
            stack.extend(reversed(arr[node])) #reversed하면 요소중 첫번째부터 확인 없으면 마지막부터 확인.

arr = {
    "A" : ["B"],
    "B" : ["A","C","D","E"],
    "C" : [],
    "D" : ["F","G"],
    "E" : [],
    "F" : ["H"],
    "G" : ["D"],
    "H" : ["F"]
}
start = "A"

bfs(arr,start)
print()
dfs(arr,start)

실행결과 (위쪽 - bfs, 아래쪽 - dfs)

qu : ['A']   visit : []
node : A
qu : ['B']   visit : ['A']
node : B
qu : ['A', 'C', 'D', 'E']   visit : ['A', 'B']
node : A
qu : ['C', 'D', 'E']   visit : ['A', 'B']
node : C
qu : ['D', 'E']   visit : ['A', 'B', 'C']
node : D
qu : ['E', 'F', 'G']   visit : ['A', 'B', 'C', 'D']
node : E
qu : ['F', 'G']   visit : ['A', 'B', 'C', 'D', 'E']
node : F
qu : ['G', 'H']   visit : ['A', 'B', 'C', 'D', 'E', 'F']
node : G
qu : ['H', 'D']   visit : ['A', 'B', 'C', 'D', 'E', 'F', 'G']
node : H
qu : ['D', 'F']   visit : ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
node : D
qu : ['F']   visit : ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
node : F

stack : ['A']   visit : []
node : A
stack : ['B']   visit : ['A']
node : B
stack : ['E', 'D', 'C', 'A']   visit : ['A', 'B']
node : A
stack : ['E', 'D', 'C']   visit : ['A', 'B']
node : C
stack : ['E', 'D']   visit : ['A', 'B', 'C']
node : D
stack : ['E', 'G', 'F']   visit : ['A', 'B', 'C', 'D']
node : F
stack : ['E', 'G', 'H']   visit : ['A', 'B', 'C', 'D', 'F']
node : H
stack : ['E', 'G', 'F']   visit : ['A', 'B', 'C', 'D', 'F', 'H']
node : F
stack : ['E', 'G']   visit : ['A', 'B', 'C', 'D', 'F', 'H']
node : G
stack : ['E', 'D']   visit : ['A', 'B', 'C', 'D', 'F', 'H', 'G']
node : D
stack : ['E']   visit : ['A', 'B', 'C', 'D', 'F', 'H', 'G']
node : E