DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

 

오늘 배워볼 내용은 탐색이다.

 

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

 

이는 여러가지 방법이 있는데, 프로그래밍에서 자주 사용하는, 그리고 가장 중요시되는 구조는 바로 DFS, BFS 이다.

 

이를 이해하기 위해서는 먼저 자료구조에 대해서 알아 볼 필요가 있다.

 

자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 말한다. 

 

대표적으로 자료구조에는 배열, 연결리스트, 스택, 큐, 트리, 그래프가 있는데, 우리가 필요한 자료구조는 스택과 큐이다.

 

스택(Stack)

"먼저 들어간 데이터가 가장 나중에 나온다"가 핵심이다. 이를 우리는 FILO(First In Last Out)라고 부른다. 

파이썬에서 스택은 기본 리스트에서 append()와 pop()을 이용하면 다른 언어의 스택과 동일하게 동작한다.

 

큐(Queue)

큐는 스택과 반대로, "먼저 들어간 데이터가 가장 먼저 나온다"가 핵심이다. 이를 FIFO(First In First Out)이라고 부른다.

큐 라이브러리를 불러와서 사용해도 되지만, 보통 Collections 모듈에서 deque를 불러와 사용한다. 왜냐하면 deque는 데이터를 넣고 뺴는 속도가 빠르고, 더 간단하기 때문이다.

 

이 두가지 자료구조만 알고 있다면 DFS와 BFS의 개념을 잘 이해할 수 있다. 

 

 

DFS(깊이 우선 탐색)

DFS의 정의는 깊은부분을 우선적으로 탐색하는 것이다. 이를 하기 위해서는 위의 자료구조인 스택을 사용하게 되는데, 코드를 간결하게 하기 위해 재귀함수를 사용하는 경우도 있다. 스택과 재귀함수는 상당히 비슷하다고 볼수가 있다. 컴퓨터 구조측면에서도 메모리가 같은 공간에 적재되기 때문이다. 필자는 재귀함수로 DFS를 구현하려고 한다.

 

DFS는 '그래프'에서 사용이 되는데, 그래프를 구현하는 방법은 인정행렬과 인접리스트 두 가지가 있다.

인접행렬은 2차원 배열을 이용해 구현하고, 인접리스트는 리스트로 그래프의 연결관계를 구현한다고 생각하면 된다.

결국 연결되어 있는 노드(점)들을 탐색하기 위해 DFS와 BFS를 배운다고 생각하면 된다.

 

인접행렬과 인접리스트에 대해서 조금 더 살펴보자면, 인접행렬은 인접리스트에 비해 메모리를 많이 사용한다. 왜냐하면 인접리스트는 연결되어있는 데이터만을 저장하고, 인접행렬은 연결되어 있지 않은 것들도 INF(무한대)의 값으로 저장하기 때문이다. 하지만 인접리스트는 인접행렬에 비해 특정 데이터가 연결되어 있는지 알기에 까다롭다. 이유는 연결된 데이터를 하나하나 확인해야 하기 때문이다.

 

위의 개념들을 이용해 연습문제를 풀어보겠다.

이와 같은 노드가 있다고 하자. 우리는 1번부터 깊이 우선 탐색을 하려고 한다. 순서를 출력하라고 문제에 주어졌을 때 우리는 어떻게 해결해야 할까?

1. 1번노드를 스택에 넣고, 방문처리를 한다.
2. 1번과 연결된 다른 노드중 가장 작은값을 스택에 넣고 방문처리를 한다.
3. 2번을 반복하다가 방문하지 않은 인접 노드가 없을 경우 스택에서 그 노드를 꺼낸다.
4. 2,3번 반복한다.

재귀함수의 해결방안은 이렇다.

   1. DFS함수에 1번 함수인자를 넣는다

   2. 1번 노드를 방문표시하고 출력한다

   3. 1번 노드의 인접한 노드 중 방문하지 않은 가장 작은 노드를 다시 dfs함수에 넣는다.

   4. 반복한다.

 

글로만 읽으면 잘 이해가 안 갈 것이다. 코드를 통해 확인해보자.

def dfs(start, visited, graph):
  graph[start] = True
  print(start, end = ' ')
  
  for i in graph[start]:
    if not visited[i]:
      dfs(i,visited,graph)
      
graph = [
            [],
            [2, 4, 5],
            [1, 3, 5],
            [2, 5, 6],
            [1, 5],
            [1, 2, 4, 6],
            [3, 5]
]

visited = [False]*9

dfs(1,visited,graph)

위의 코드에서는 방문표시를 해줘야 겹치지 않게 숫자를 출력할 수 있다. 문제에 따라 방문표시를 해줘야하는지, 아니면 다른 방법으로 구별할 수 있는지를 파악하고 문제에 접근하는 것이 중요하다.

 

BFS

위의 DFS는 재귀함수를 통해 구현했다. 스택으로 하는 것보다 더 간결하고 효율적으로 보였기 때문이다.

BFS는 큐를 이용해서 구현할 것이다. 정확히는 Collections라이브러리의 deque를 가져와서 큐를 구현할 것이다. 

 

위의 문제를 BFS를 통해 풀어보자.

1. 큐에 시작 노드를 넣고 방문처리를 한다.
2. 큐가 비어있을 때까지 큐에넣은 노드와 인접한 노드를 불러오고 방문처리하고 출력하고를 반복한다.

코드는 이렇다.

 

from collections import deque
def bfs(start, visited, graph):
  queue = deque([start])
  graph[start] = True
  
  while queue:
    x = queue.popleft()
    print(x, end = ' ')
    for i in graph[x]:
      if not visited[i]:
        visited[i] = True
        queue.append(i)
        
graph = [
            [2, 4, 5],
            [1, 3, 5],
            [2, 6],
            [1, 5],
            [1, 2, 4, 6],
            [3, 5]
]

visited = [False] * 9
bfs(1, visited, graph)

방문했는지를 검사하기 위해 visited를 넣는 것은 문제를 보고 센스있게 쓰도록 하자.