너비 우선 탐색(BFS)

너비 우선 탐색(Breadth-First Search)

• 그래프

  • 연결의 집합을 모형화한 것
  • 그래프는 정점(node)와 간선(edge)로 이루어진다. 이어진 정점을 이웃(neighbor)이라고 한다.
  • 그래프에는 방향 그래프와 무방향 그래프가 있다. 무방향은 화살표가 없고 서로 상호 관계가 있다는 뜻이다.

   

• 너비 우선 탐색

  • 그래프를 대상으로 하는 탐색 알고리즘이다. 다음과 같은 질문을 던지면 도움이 된다.

    1. 정점 A에서 B로 가는 경로가 존재하는가?(ex. 내 네트워크 중 바나나칩 판매상이 있는가?)
    2. 정점 A에서 B로 가는 최단 경로는 무엇인가?(ex. 누가 가장 가까운 바나나칩 판매상인가?)

    네트워크를 통해 바나나칩 판매상을 찾으려고 한다고 가정했을 때, 내 친구부터 탐색하고, 친구 중에 없으면 친구의 친구를 탐색한다. 그 중에서도 없으면 친구의 친구의 친구를 찾는 식으로 탐색한다.

  • 너비 우선 탐색은 최단 경로를 찾는 데에 도움을 준다. 예를 들어 2촌보다는 1촌에서 원하는 것을 찾는 것이 더 바람직하다. 이를 위해서는 탐색을 위한 목록을 작성할 때에 1촌을 2촌보다 앞에 두어야한다. 이를 위한 자료구조를 큐(Queue)라고 한다.

   

• 큐(대기열)

  • 큐는 큐 안의 원소에 임의 접근할 수 없다. (그런 점에서 스택과 비슷하다. 스택은 push, pop만 할 수 있는 자료구조)
  • 큐에는 삽입(enqueue)과 제거(dequeue)라는 두 가지 연산이 있다.
  • 큐는 스택과 달리 선입선출(First in First out)이다.

 

• 예시(바나나칩 판매상을 찾는 문제)

  1. 확인할 사람의 명단을 넣을 큐를 준비한다.

  2. 큐에서 한 사람을 꺼낸다. (가장 앞의 사람)

  3. 그 사람이 바나나칩 판매상인지 확인한다.

  4. a. 만약 바나나칩 판매상이면 작업이 완료된다.

     b. 만약 아니라면 그 사람의 친구를 명단에 추가한다. (큐의 뒤에 추가된다)

  5. 반복문
  6. 만약 큐가 비어있으면 네트워크에는 바나나칩 판매상이 없다.

   

  • 중복된 친구가 있는 경우

    만약 친구 A와 친구 B가 C를 공통으로 친구로 삼고 있다면, C는 두 번 큐에 들어가게 된다. 이 경우 한 번 확인되면 다시 탐색되지 않도록 표시해야 한다. 만약 그렇게 하지 않으면 무한 루프에 빠질 수도 있다. (ex. 나의 유일한 친구가 C이고 C의 유일한 친구 또한 나인 경우, 그리고 둘 다 판매상이 아닌 경우)