파이썬 알고리즘 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

DFS (깊이 우선 탐색)

출처 - https://en.wikipedia.org/wiki/Depth-first_search

깊이 우선 탐색의 특징

1. stack 자료 구조를 사용한다

   1.1. stack 은 Last In First Out 의 자료구조이다. 다시말해, 먼저들어 온 것이 가장 늦게 나가는 자료구조 이다.

   1.2. 이러한 LIFO 자료 구조를 갖고 있는 것이 컴퓨터의 재귀함수 처리 방식이다.

2. 탐색을 할 때, 시작 노드를 스택에 쌓는다.
   즉, 시작 노드를 먼저 함수를 실행하고,
   시작 노드와 연결된 자손노드 중에서, 방문하지 않은 모든 인접(자손) 노드를 스택에 넣는다. (함수를 실행한다.)

+ 함수는 실행시, 함수 실행을 시킨 노드를 방문 처리하고, 현재 노드에서 다시 한번 방문하지 않은 인접(자손)노드를 스택에 넣는다(자손노드를 현재 노드로 실행하는 함수를 실행한다.)

3. 이렇게 하면, 모든 노드를 방문하기 전까지 계속해서 스택이 쌓인다.

4. 방문하지 않은 자손 노드가 없으면 스택에서 최상단 노드를 꺼낸다.(즉, 함수 실행이 종료가 되며, 가장 나중에 들어온 함수 실행이 종료 된다.)

>>>  def dfs(graph, node, visited):
        visited[node] = True
        answer.append(node)

        for idx in graph[node]:
            if not visited[idx]:
                dfs(graph, idx, visited)

    dfs(graph, 1, visited)

    return answer
    
>>> graph = [
        [],
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]
    ]
>>> dfs(graph, 1, [False] * len(graph))

### answer = [1, 2, 7, 6, 8, 3, 4, 5]

BFS (너비 우선 탐색)

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89

깊이 우선 탐색은 말그대로 아래로 내려가며 탐색하는 알고리즘이면, 너비 우선 탐색은 가까운 노드부터 탐색하는 알고리즘 이다.

너비 우선 탐색의 특징은

1. queue 자료구조를 사용하는데에 있다.
   1.1. queue 는, First In First Out 의 구조를 갖고 있다.
   1.2. python 의 deque를 통해서 queue 자료구조를 구현 할 수 있다.
2. 탐색을 시작하면, 시작노드를 큐에 넣고 방문 처리를 한다.
3. 큐에 더이상 노드가 없을 때 까지 큐에서 가장 먼저 들어온 노드를 빼고, 그 노드의 인접 노드를 탐색한다
   3.1 인접노드 중 에서 방문 처리 되지 않은 모든 노드를 큐에 넣고 방문 처리를 해준다.
4. 모든 노드가 방문 처리가 될 때 까지 계속해서 3번 과정을 반복한다

>>> def bfs(graph, start_node):
        import collections
        visited = {x: False for x in graph}
        answer = [start_node]
        queue = collections.deque([])

        queue.append(start_node)
        visited[start_node] = True

        while queue:
            current_node = queue.popleft()

            for node in graph[current_node]:
                if not visited[node]:
                    visited[node] = True
                    queue.append(node)
                    answer.append(node)

        return answer
        
        
>>> graph = {
        'A': ['B'],
        'B': ['A', 'C', 'H'],
        'C': ['B', 'D'],
        'D': ['C', 'E', 'G'],
        'E': ['D', 'F'],
        'F': ['E'],
        'G': ['D'],
        'H': ['B', 'I', 'J', 'M'],
        'I': ['H'],
        'J': ['H', 'K'],
        'K': ['J', 'L'],
        'L': ['K'],
        'M': ['H']
    }
    
>>> bfs(graph, 'A')


### ['A', 'B', 'C', 'H', 'D', 'I', 'J', 'M', 'E', 'G', 'K', 'F', 'L']