DFS

• DFS : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘, 시간복잡도 O(n)

• 그래프 : 노드와 간선이루어짐

  • 인접 행렬 방식 : 2차원 배열로 그래프 연결 관계 표현(메모리 많이, 속도 빠름)
  • 인접 리스트 방식 : 리스트로 그래프의 연결 관계 표현(메모리 적게, 속도 느림)

• DFS의 동작 과정

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 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],
      [4, 5],
      [3, 5],
      [3, 4],
      [7],
      [2, 6, 8],
      [1, 7]
  ]
  
  visited = [False] * 9
  
  dfs(graph, 1, visited)

  BFS

• BFS : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘, 큐 자료구조를 이용함, O(n)

• deque 라이브러리를 이용하는것이 좋으며, DFS보다 수행 시간이 빠르다.

• BFS의 동작 과정

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

from collections import deque


def bfs(graph, start, visited):
    visited[start] = True
    queue = deque([start])
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


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

visited = [False] * 9

bfs(graph, 1, visited)

결론

1차원 배열이나 2차원 배열은 그래프 형태로 생각하면 수월하게 문제를 풀 수 있다. 게임 캐릭터의 상하좌우 이동 문제도 그래프 형태로 바꿔서 생각할 수 있다.