DSA (데이터구조와 알고리즘) 면접 질문 - "BFS가 뭔가요?"

BFS를 다음과 같이 알아보겠다:

- graph를 traverse 하는 알고리즘이다.

- bfs가 쓰이는 때와 예시 코드

 

graph를 traverse 하는 알고리즘이다

graph는 무엇인가:

- node와 edge로 이루어진 정보이다

 

graph는 어떤 자료구조로 표현하는가:

예시로 다음과 같은 graph가 주어졌다면
    A
   / \
  B   C
   \ /
    D

- adjacency list:

graph = {
  'A': {'B', 'C'},
  'B': {'A', 'D'},
  'C': {'A', 'D'},
  'D': {'B', 'C'}
}

# graph는 python dict (dict of sets)
# graph['A']는 python set
# 공간복잡도: 노드 저장하는데 필요한 공간 + 간선저장하는데 필요한 공간 = O(V) + O(2E) = O(V + E) # 상수 무시

- adjacency matrix:

graph = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 1],
  [0, 1, 1, 0]
]

# graph는 2차원 리스트
# graph[i]는 1차원 리스트
# 공간복잡도: O(n^2)

 

travese 방식:

1. 어떤 한 시작점을 주었을 때, 시작점을 추후 갈 것으로 기록된 node로 등록
2. 추후 갈 것으로 기록된 node 들 중 가장 먼저 기록한 node 방문
3. 방문한 node에서 갈 수 있는 node 들을 추후 갈 것으로 기록. 단, 이미 방문한 node는 기록하지 않음.
4. 2번으로 다시 방문
5. traverse를 완료한 시점은 추후 갈 것으로 기록된 node가 없는 것으로 알 수 있음

queue 활용:

• 추후에 갈 node 들을 기록하기 위해 사용
• queue는 first in first out 특징을 갖고 있음
• python queue:

from collections import deque

# deque: double-ended queue
## 중복 허용
## 순서 유지
## search: O(n)
## insert/delete: O(1)

# create
queue = deque()

# example constructors
## deque([])
## deque([1,2,3])
## deque((1,2,3)) == deque([1,2,3])

# in
queue.append(1)

# in list
queue.extend([])

# out
x = queue.popleft()

 

set 활용:

• 위에서 "단, 이미 방문한 node는 기록하지 않음" 을 위해서 사용
• python set:

# set
## 중복 제거
## 순서 없음
## search: O(1)
## insert/delete: O(1)

visited = set()

# insert
visited.add(1)

# insert each element in a list
visited.update([2,3])

# delete
visited.remove(1) # raise error if not existing
visited.discard(1) # does not raise error

# delete all
visited.clear()

# remove from memory
del visited

# check if in visited
if node not in visited:
  # add to queue

 

bfs:

• python:

# queue (deque)
# visited (set)

# graph (dict of sets)

# 어떤 한 시작점을 주었을 때, 시작점을 추후 갈 것으로 기록된 node로 등록
# 추후 갈 것으로 기록된 node 들 중 가장 먼저 기록한 node 방문
# 방문한 node에서 갈 수 있는 node 들을 추후 갈 것으로 기록. 단, 이미 방문한 node는 기록하지 않음.
# 2번으로 다시 방문
# traverse를 완료한 시점은 추후 갈 것으로 기록된 node가 없는 것으로 알 수 있음

from collections import deque

graph = {
  'A': {'B', 'C'},
  'B': {'A', 'D'},
  'C': {'A', 'D'},
  'D': {'B', 'C'}
}

queue = deque()
visited = set()

# 어떤 한 시작점을 주었을 때, 시작점을 추후 갈 것으로 기록된 node로 등록
start = 'A'

queue.append(start)
visited.add(start)

# traverse를 완료한 시점은 추후 갈 것으로 기록된 node가 없는 것으로 알 수 있음
while queue:
    # 추후 갈 것으로 기록된 node 들 중 가장 먼저 기록한 node 방문
    node = queue.popleft()
    print(node)

    # 2번으로 다시 방문
    for neighbor in graph[node]:
        # 방문한 node에서 갈 수 있는 node 들을 추후 갈 것으로 기록. 단, 이미 방문한 node는 기록하지 않음.
        if neighbor not in visited:
            queue.append(neighbor)
            visited.add(neighbor)

 

bfs가 쓰이는 때와 예시 코드

bfs 용도:

• 최단거리 찾을 때 사용
• 크롤링

최단거리 찾을 때:

• 사용하는 특징:
  • bfs는 거리가 가까운 순서대로 visit하고 다음에 방문할 neighbor를 add 한다
  • 어떤 특정 노드를 visit 하였다면, 그때까지 건넜던 edge의 수는 최소라고 볼 수 있다
  • bfs는 edge 1번 건너서 갈 수 있는 node 방문, 2번 건너서 갈 수 있는 방문 ... 이 순서대로 건너기 때문에 어느 node에 방문 했다면 그때 걸렸던 edge 의 수는 최소 일 수 밖에 없다
•  python:
  • queue에 해당 node를 갈 때 까지 필요했던 edge 수 또한 기록
    • tuple 사용. tuple 예: (start, 0)
  • end 조건은 목적지를 도착했을 때

from collections import deque

graph = {
  'A': {'B', 'C'},
  'B': {'A', 'D'},
  'C': {'A', 'D'},
  'D': {'B', 'C'}
}

queue = deque([])
visited = set([])

start = 'A'
end = 'D'

queue.append((start, 0))
visited.add(start)

while queue:
    node, distance = queue.popleft()
    if node == end:
        print(distance)
        exit()
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            queue.append((neighbor, distance + 1))
            visited.add(neighbor)

 

크롤링:

• 사용하는 특징:
  • 루트 페이지 (예: index.html) 에서 시작해서 그 페이지에서 타고 갈 수 있는 링크들을 수집하고
  • 수집한 링크들 중 한페이지를 가고 추후 갈 링크들로 수집해 두고
  • 이전에 수집한 순서대로 다시 수집한 링크들 중 한페이지를 간다
  • 결과적으로, sitemap은 root에서 가까운 순부터 먼 순으로 생긴다