[Algorithm] 3. DFS & BFS

DFS & BFS

• 대표적인 그래프 탐색 알고리즘이다.
• 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.
• DFS & BFS 를 알기전에 반드시 알아야 할 자료구조로는 스택과 큐가 있다.

스택(Stack)

• 먼저 들어온 데이터가 나중에 나가는 형식(LIFO)의 자료구조이다.
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
• 파이썬에서는 list 자료형으로 구현할 수 있다. 삽입할 때는 append(), 삭제할 때는 pop()을 쓰면 된다.

큐(Queue)

• 먼저 들어온 데이터가 먼저 나가는 형식(FIFO)의 자료구조이다.
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다.
• 파이썬에서 collections 의 deque 를 사용할 수 있다. 원소를 삽입할 때는 append(), 삭제할 때는 popleft() 를 사용하면 된다.
• 리스트로도 기능적으로 큐를 구현할 수 있지만 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있다. 따라서 큐를 이용할 때는 deque 를 이용하는 것이 좋다.
• 큐의 순서를 바꿀 때는 reverse() 로 할 수 있다.

DFS (Depth-First Search)

• 깊이 우선 탐색. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• 스택 자료구조 혹은 재귀 함수를 이용하며, 구체적인 동작과정은 아래와 같다.
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
• 매번 최상단 원소를 기준으로 해서 방문하지 않은 인접 노드가 있으면 그 인접한 노드로 방문을 수행하는 것이다.
• 실제로 DFS 는 최대한 깊게 들어가는 형태로 동작하기 때문에 스택 자료구조 대신에 재귀 함수로도 가능하다.

• DFS 는 그래프(2차원 리스트 등)에 대한 정보와 방문 정보를 가지고 만들어낼 수 있다.

    def dfs(graph, v, visited):
        # 현재 노드를 방문 처리
        visited[v] = True
        print(v, end=' ')
        # 현재 노드와 연결된 인접 노드를 재귀적으로 방문
        for i in graph[v]:
            if not visited[i]:
                dfs(graph, i, visited)
                          
    graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
    ]
      
    # 각 노드가 방문된 정보를 표현(1차원 리스트)
    visited = [False] * 9
      
    dfs(graph, 1, visited)
  

BFS (Breadth-First Search)

• 너비 우선 탐색. 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
• 큐 자료구조를 이용하며, 구체적인 동작과정은 다음과 같다.
  1. 탐색 시작 노드를 큐에 삽입하고 방문처리 한다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
• DFS 는 인접 노드 중 방문하지 않은 노드를 한번씩 스택에 넣으면서 방문을 수행하는데, BFS 는 인접한 노드를 전부 큐에 넣는다.
• BFS 는 특정 조건에서의 최단 경로 문제를 해결하기 위한 목적으로 효과적으로 사용될 수 있다.

• 즉 BFS 는 각 간선의 비용이 모두 동일한 상황에서 최단 거리 문제를 해결하기 위한 목적으로도 사용할 수 있다. 왜냐하면 BFS 결과를 보면 거리가 가까운 것들이 앞에 탐색되고 거리가 가장 먼 것이 맨 마지막에 탐색되기 때문이다.

    from collections import deque
      
    def bfs(graph, start, visited):
        # deque 라이브러리를 이용하여 큐 구현
        queue = deque([start])
        # 현재 노드를 방문 처리
        visited[start] = True
        # 큐가 빌 때까지 반복
        while queue:
            # 큐에서 하나의 원소를 뽑아 출력
            v = queue.popleft()
            print(v, end=' ')
            # 아직 방문하지 않은 인접한 원소들을 모두 큐에 삽입하고 방문처리
            for i in graph[v]:
                if not visited[v]:
                    queue.append(i)
                    visited[i] = True
                      
    graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
    ]
      
    # 각 노드가 방문된 정보를 표현(1차원 리스트)
    visited = [False] * 9
      
    bfs(graph, 1, visited)
  

맨 위로 이동 ↑