지도 앱을 이용해 최단 경로를 찾거나 주변에 가까운 음식점은 어떤 것이 있는지
같은 기능들 한 번씩은 사용해 보셨죠. 어떤 원리가 있는 지 궁금하신 적 있나요?
이 안에는 프론트, 백, 데이터프로세싱, GPS등 여러 기술이 복잡하게 있지만
그 중 백에서는 BFS을 기반한 알고리즘이 쓰이는 경우가 많습니다.
과연 BFS란 머고 어떤 기능으로 위 기능들을 할 수 있는지 알아보겠습니다.

BFS는 어떤 기능을 하나요?

BFS는 길찾기 또는 주변탐색 같은 노드탐색기능을 수행할 수 있습니다.
비슷한 기능을 수행하는 알고리즘으론 DFS(depth first search)가 있습니다.

BFS는 Breath-First-search의 약자로 너비-우선-탐색을 의미하는데요.
너비를 우선 탐색하기 때문에, 가장 가까운 노드 탐색이나, 주변에 있는 노드를 탐색
하는 경우는 DFS보다 좀 더 효율적이라는 장점을 가집니다!

이 중 ‘가장 가까운 노드 탐색’ 기능을 예와 함께 자세히 설명하겠습니다.

철수가 여행 중 배가 고파 짜장면을 먹을려고 하는데, 이 동네에는 3개의 중국집이 있습니다.
철수는 너무 배가 고파서 현재 위치에서 가장 가까운 중국집에 가서 짜장면을 먹으려고 합니다.

위는 동네의 지도이고 철수는 어떻게 하면 효율적으로 가장 가까운 중국집을 찾을까요?
※ 다음으로 넘어가기 전에 혼자 한 번 고민해봅시다!

brute-force하게 해봅시다.

일단 철수 위치에서 갈 수 있는 모든 노드를 조사하고 그 노드가 중국집이라면
그 거리 기록하고, 기록한 거리를 모두 비교해서 가까운 중국집을 알아내는 방법입니다.

위처럼 구하면, 이 동네에서 현 위치에서 가장 가까운 중국집은 황룡반점이다.
라는 것을 알 수 있고, 철수는 현 위치에서 1M 떨어진 청룡반점으로 갈 것 입니다.

하지만 이는 모든 노드와 길을 가봐야지 최단 거리를 알 수 있다는 것이죠.
만약 동네가 커질수록, 즉 Nodes와 edges가 많아질수록 굉장히 비효율적이 됩니다.
이 때 time-complexity를 구해보면, O(N+M) 입니다.
(이 떄, N = nodes의 수, M = Edges의 수 = 길의 수)

이 비효율성을 해결하기 위해서 BFS라는 알고리즘을 고안하게 되었습니다.

BFS:

BFS를 이용한 풀이법은 거리를 기준으로 Greedy하게 문제를 접근해서 푸는 것입니다.
풀어 말하면, 가까운 거리의 노드부터 차례 차례 구하다 보면 가장 먼저 만난 노드가 정답이다.
라는 아이디어인데, 먼저, 거리를 기준으로 노드를 구한다는 것을 설명하겠습니다.

거리를 기준으로 노드를 구하다는 것은 그림으로 표현하면 아래와 같습니다.

1번 경우: 먼저 거리가 1m인 Node들을 구하는 경우입니다.

2번 경우: 거리가 2m인 Node 들을 구하는 경우입니다.

3번 경우: 거리가 3m인 Node들을 구하는 경우입니다.

우리는 위의 BFS과정에서 약간의 직관을 사용하면 문제를 쉽게 풀 수 있습니다.
바로 첫 번쨰의 경우만 진행하고 두 번쨰, 세 번째 경우는 생략한다.라는 것입니다.
첫 번째 경우에서 중국집을 만나면, 그 중국집이 바로 가장 가까운 중국집입니다.
이유는 다음 경우에서의 중국집들은 이 중국집보다 멀리 있을 수 밖에 없기 때문입니다.

BFS의 장단점:

장점:
위처럼 최단거리 노드를 탐색하는 경우에는 정말 특화되어있습니다.
Time-complexity는 지도의 구성(Topology)에 따라 다르지만 기존의 O(N+M) 보다는
훨씬 좋은 Time-complexity를 보유할 수 있습니다.

알고리즘이 간단하고 딴 곳에 쓰기도 좋아서 다른 알고리즘에도 자주 쓰이기 좋습니다.
대표적으로 다익스트라 알고리즘, Kruaskal 알고리즘에서 BFS를 이용합니다.

단점:
경우에 따라 BFS를 썻을 때 논리 구조가 복잡해지고 구현하기 쉽지 않을 수 있습니다.
이는 BFS가 각 Node별로 Parallize하게 진행되기 때문입니다.
※ Parallel programming을 할 수 있기 때문에, 장점으로 될 수 있겠네요

실제 구현 by Python

import os
import sys
from collections import defaultdict

def BFS(nodes, edges):
  #make edges list
  adj_list = defaultdict(list)
  for edge in edges:
    node1, node2 = edge
    adj_list[node1].append(node2)
    adj_list[node2].append(node1)

  #bfs
  Q = []; Q.append('철수 위치')
  visited = set()

  while Q:
    cur_node = Q.pop(0)
    if cur_node in visited: continue
    visited.add(cur_node)

    if cur_node[-2:] == '반점': return cur_node # 중국집
    for next_node in adj_list[cur_node]: Q.append(next_node)