[알고리즘] - DFS & BFS 정리

Graph

그래프는 정점(vertex)과 이들을 연결하는 간선(edge)으로 이루어진 데이터 구조를 말합니다. 그래프는 지도나 인터넷과 같은 물리적인 연결 관계를 나타내기 위해 사용되기도 하지만 그 외 다양한 추상적인 연관성을 나타내기 위해서도 사용됩니다.

이러한 그래프 중 간선에 방향성이 있는 그래프를 방향(direction)이 있다는 의미로 directed graph라 하며, 반대로 간선에 방향성이 없는 그래프를 undirected graph라 합니다.

그래프 탐색 방법에는 대표적으로 2가지가 있습니다. 깊이 우선 탐색인 DFS와 너비 우선 탐색인 DFS가 있습니다. 아래에는 2가지 방법에 대한 설명을 적었습니다.

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

DFS 방법은 root에서 시작하여 가장 깊은 곳까지 탐색한 후 돌아서 모든 정점을 방문하는 방법입니다. DFS의 목표는 탐색을 시작할 정점 s가 주어졌을 때, s로부터 도달 가능한 모든 정점을 방문해 보며 어느 곳이 도달 가능한지를 기록하는 것입니다. 또한 이 과정에서 거쳐온 경로도 기록합니다.

구현은 재귀 또는 스택을 활용하여 구현 가능합니다. 깊이 우선 탐색의 특성상 재귀가 적합하며, 스택은 명시적으로 사용할 수 있습니다.

def dfs(graph, visited, node):
  visited[node] = True
  for connectedNode in graph[node]:
    if not visited[connectedNode]:
      dfs(graph, visited, connectedNode)
  return visited

위의 코드는 재귀를 활용하여 DFS를 구현한 것입니다.

1. graph: 그래프를 나타내는 인접 리스트입니다. 각 노드에서 연결된 노드들의 리스트로 표현되어 있습니다.
2. visited: 노드의 방문 여부를 나타내는 리스트입니다. 각 인덱스는 노드를 나타내며, 방문한 노드는 True, 아직 방문하지 않은 노드는 False로 표시됩니다.
3. node: 현재 탐색 중인 노드입니다. 함수가 호출될 때마다 현재 노드에서 연결된 노드들을 재귀적으로 탐색합니다.
4. visited[node] = True: 현재 노드를 방문 처리합니다.
5. for connectedNode in graph[node]:: 현재 노드에서 연결된 모든 노드에 대해 반복합니다.
6. if not visited[connectedNode]:: 연결된 노드가 아직 방문되지 않았다면 아래 코드를 실행합니다.
7. dfs(graph, visited, connectedNode): 연결된 노드를 시작으로 다시 DFS를 호출하여 재귀적으로 탐색을 진행합니다.
8. return visited: 모든 연결된 노드를 방문한 후 최종적으로 방문된 노드의 상태를 반환합니다.

위의 코드는 인접 리스트의 형식으로 구현이 된 코드입니다. 그래서 인접 리스트로 표현된 그래프의 경우[V: 노드 수, E: 간선 수] O(V + E)입니다.

1. 각 노드의 방문 여부 확인 (O(V)): 각 노드마다 한 번씩 방문 여부를 확인합니다.
2. 인접 리스트를 통한 간선 탐색 (O(E)): 간선의 수만큼 반복문이 돌아가므로 O(E)입니다.

따라서, 전체 시간 복잡도는 O(V + E)가 됩니다. 이는 간선의 수와 노드의 수에 비례하는 선형 시간 복잡도입니다.

장점:

1. 메모리 효율성:
   • DFS는 깊이 우선 탐색의 특성상 스택 또는 재귀를 사용하여 구현되기 때문에, 현재 경로 상의 노드들만을 기억하면 되므로 메모리 사용이 효율적입니다.
2. 미로 및 경로 문제 해결:
   • DFS는 미로와 같은 문제에서 한 경로를 최대한 깊게 탐색하므로, 미로를 탈출하거나 특정 경로를 찾는 데 유용합니다.
3. 연결 요소 및 사이클 탐지:
   • 그래프에서 연결 요소나 사이클을 찾는 데 DFS를 사용할 수 있습니다. 한 노드에서 시작하여 모든 연결된 노드를 탐색하므로, 그래프의 구조를 파악하기 용이합니다.

단점:

1. 최단 경로 탐색 문제:
   • DFS는 한 경로를 깊게 탐색하므로, 최단 경로를 찾는 문제에 적합하지 않습니다. 최단 경로 문제에는 BFS가 더 적합합니다.
2. 무한 루프에 빠질 수 있음:
   • 그래프에 순환 구조가 있거나, 잘못된 조건을 설정할 경우 무한 루프에 빠질 수 있습니다. 이를 방지하기 위해 방문한 노드를 마킹하거나, 적절한 종료 조건을 설정해야 합니다.
3. 경로의 수가 많을 때 비효율성:
   • 경로가 많은 경우 모든 경로를 탐색하는 데 시간이 오래 걸릴 수 있습니다. 이런 경우에는 다른 알고리즘을 고려해야 합니다.
4. 최악의 경우 시간 복잡도가 높을 수 있음:
   • 그래프의 구조에 따라서는 최악의 경우에 탐색 시간이 길어질 수 있습니다. 특히, 균일하지 않은 분포의 그래프에서는 성능이 떨어질 수 있습니다.

BFS (Breath First Search) - 너비 우선 탐색

BFS 방법은 root에서 시작하여 인접한 모든 정점을 먼저 탐색한 후, 그 다음 레벨의 정점들을 차례로 방문하며 진행하는 방법입니다. BFS의 목표는 탐색을 시작할 정점 s가 주어졌을 때, s로부터 도달 가능한 모든 정점을 방문해 보며 어느 곳이 도달 가능한지를 기록하는 것입니다. 또한 이 과정에서 거쳐온 경로도 기록합니다.

큐(Queue) 자료구조를 사용하여 구현됩니다.

from collections import deque

def bfs(graph, visited, node):
  queue = deque()
  queue.append(node)  
  visited[node] = True
  while queue:
    start = queue.popleft()
    for connectedNode in graph[start]:
      if not visited[connectedNode]:
        queue.append(connectedNode)
        visited[connectedNode] = True
  return visited

위의 코드는 큐를 활용하여 BFS를 구현한 것입니다.

1. 큐 초기화 및 시작 노드 추가:
   • queue = deque()를 통해 큐를 초기화합니다.
   • queue.append(node)를 통해 시작 노드를 큐에 추가합니다.
   • visited[node] = True를 통해 시작 노드를 방문 처리합니다.
2. 큐가 비어있을 때까지 반복:
   • while queue:를 통해 큐가 비어있지 않은 동안 반복합니다.
3. 큐에서 노드 추출 및 방문 처리:
   • start = queue.popleft()를 통해 큐에서 노드를 추출합니다.
   • visited[start] = True를 통해 현재 노드를 방문 처리합니다.
4. 인접한 노드들을 큐에 추가하고 방문 처리:
   • for connectedNode in graph[start]:를 통해 현재 노드와 연결된 모든 노드에 대해 반복합니다.
   • if not visited[connectedNode]:를 통해 연결된 노드가 아직 방문되지 않았다면 아래 코드를 실행합니다.
   • queue.append(connectedNode)를 통해 연결된 노드를 큐에 추가합니다.
   • visited[connectedNode] = True를 통해 연결된 노드를 방문 처리합니다.
5. 방문된 노드 상태 반환:
   • return visited를 통해 모든 연결된 노드를 방문한 후 최종적으로 방문된 노드의 상태를 반환합니다.

BFS의 시간 복잡도 또한 O(V+E)입니다.

1. 각 노드의 방문 여부 확인 (O(V)): 각 노드마다 한 번씩 방문 여부를 확인합니다. 따라서 노드의 수에 비례하는 시간이 소요됩니다.
2. 인접 리스트를 통한 간선 탐색 (O(E)): 인접 리스트를 통해 간선의 수만큼 반복문이 돌아가므로, 간선의 수에 비례하는 시간이 소요됩니다.

따라서 전체 시간 복잡도는 O(V + E)가 됩니다. 이는 간선의 수와 노드의 수에 비례하는 선형 시간 복잡도를 나타냅니다.

장점:

1. 메모리 효율성:
   • BFS는 너비 우선 탐색의 특성상 큐를 사용하여 구현되기 때문에, 현재 레벨의 노드들만을 기억하면 되므로 메모리 사용이 효율적입니다.
2. 미로 및 최단 경로 문제 해결:
   • BFS는 미로와 같은 문제에서 최단 경로를 찾는 데 유용합니다. 레벨 순서대로 탐색하기 때문에 처음으로 도달한 경로가 최단 경로입니다.
3. 연결 요소 및 사이클 탐지:
   • 그래프에서 연결 요소나 사이클을 찾는 데 BFS를 사용할 수 있습니다. 레벨 순서대로 탐색하면서 연결된 모든 노드를 탐색할 수 있습니다.

단점:

1. 메모리 사용량이 크다:
   • 모든 현재 레벨의 노드를 큐에 저장해야 하므로 메모리 사용량이 큽니다.
2. 경로의 수가 많을 때 비효율성:
   • 경로가 많은 경우 모든 경로를 탐색하는 데 시간이 오래 걸릴 수 있습니다.
3. 최악의 경우 시간 복잡도가 높을 수 있음:
   • 그래프의 구조에 따라서는 최악의 경우에 탐색 시간이 길어질 수 있습니다.

💡 BFS는 항상 최단 경로이지만, DFS는 최단 경로 일수 도 있고, 아닐 수도 있습니다.