Hello Coding 알고리즘

6. 너비 우선 탐색 BFS Breadth-First Search

그래프 graph

❗ X축과 Y축을 가지고 있는 그래프가 아니다!

그래프에 대해 설명 후, 너비 우선 탐색 알고리즘을 배운다.

너비 우선 탐색은 매우 유용한 알고리즘이다.

• 최단 경로 문제 shortest-path problem
  • 가장 짧은 것을 찾아야 하는 문제.
  • 최단 경로 문제는 너비 우선 탐색 알고리즘으로 풀 수 있다.
  • 예1 : 친구 집까지 가는 최단 경로
  • 예2 : 체스에서 체크 메이트를 만드는 최소한의 수

그래프란?

: 연결의 집합을 모형화한 것.

그래프는 항목들이 서로 어떻게 연결되어 있는지를 모형화하는 방법이다.

ⓐ→ⓑ

• 정점 node : 동그라미 (ⓐ, ⓑ)
  • 간선으로 바로 이어진 정점을 이웃neighbor이라고 한다.
  • a와 b는 이웃이다.
• 간선 edge : 선(→ 또는 -)
• 방향 그래프 directed graph
  • 화살표(방향성)을 가지는 그래프.
  • →로 이어짐 : 화살표 방향으로 관계를 가짐
  • ⓑ는 ⓐ의 이웃이지만, ⓐ는 ⓑ의 이웃이 아님
• 무방향 그래프 undirected graph
  • 화살표(방향성)을 가지지 않는 그래프.
  • -로 이어짐 : 상호 관계를 나타냄
  • ⓐ와 ⓑ는 서로 이웃임

너비 우선 탐색 (BFS, Breadth-First Searh)

: 그래프를 대상으로 하는 탐색 알고리즘.

너비 우선 탐색을 통해 아래의 두 질문에 대답할 수 있다.

• 정점 A에서 정점 B로 가는 경로가 존재하는가?
• 경로가 존재한다면, 최단 경로는 무엇인가?

예제 : 망고 판매상 찾기. (134페이지부터)

나는 망고 농사를 짓고 있고, 망고를 팔아 줄 사람을 찾아야 한다.

내 친구(1촌) 중에 망고 판매상이 있는지 알아본다.

없다면 내 친구의 친구(2촌) 중에 망고 판매상이 있는지 알아본다.

...

망고 판매상을 찾을때까지 모든 친구들을 찾는다.

• 최단 경로 찾기
  • 가장 가까운 망고 판매상을 어떻게 찾을 수 있는가?
  • 방법1 : 1촌 중에서 망고 판매상이 없을 때만 2촌을 탐색한다.
  • 방법2 : 탐색 리스트에 1촌부터 모두 추가한 후 2촌을 추가한다.
    • 목록 순서대로 탐색할 때만 가능
    • 이 때 필요한 자료구조가 큐queue 이다.

큐 (queue, 대기열)

버스 정류장에 줄을 설 때와 같은 원리. 먼저 줄을 선 사람부터 버스에 탈 수 있다.

• 큐 안의 원소에는 임의로 접근할 수 없다. 큐에는 삽입, 제거라는 두 가지 연산만 존재한다.
  • 삽입 enqueue : 큐의 맨 뒤에 항목을 더한다
  • 제거 dequeue : 큐의 맨 앞에서 항목을 꺼낸다

즉 반드시 먼저 추가된 사람들을 먼저 꺼내서 탐색하는 자료구조.

• 선입선출, FIFO(First In First Out) 자료구조라고도 한다.

큐(선입선출, FIFO) <-> 스택(후입선출, LIFO, Last In First Out)

너비 우선 탐색 - 그래프 구현

가장 먼저 코드로 그래프를 구현해야 함 - 해시테이블(맵)을 활용.

• 키 : 노드

• 값 : 그 노드가 이웃한 노드

• 예를 들어 내 친구가 앨리스, 밥, 클레어라면

  • 키 : 나, 값 : {앨리스, 밥, 클레어} 배열.

• 클레어의 친구가 톰, 조니라면

  • 키 : 클레어, 값 : {톰, 조니} 배열.

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["clair"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

너비 우선 탐색 - 알고리즘 구현

너비 우선 탐색 알고리즘의 과정은 다음과 같다

(망고 판매상 찾기 예제에서)

1. 확인할 사람의 명단을 넣을 큐를 준비한다
2. 큐에서 한 사람을 꺼낸다
3. 이 사람이 망고 판매상인지 아닌지 확인한다
   1. 맞다면 작업 종료
   2. 아니라면 이 사람의 이웃을 모두 큐에 추가한다
4. 2.로 되돌아간다
5. 큐를 모두 탐색해 큐가 비어 있다면, 이 네트워크에는 망고 판매상이 없는 것.

(아래는 파이썬 구현 코드 - 양방향 큐인 deque 사용)

from collections import deque

def search(name):
    search_queue = deque() ## 큐 (탐색 목록)
	search_queue += graph[name] ## name의 모든 1촌을 큐에 추가
    searched = [] ## 이미 확인한 사람을 추적하기 위한 배열

	while search_queue: ## 큐가 비어있지 않은 한 계속 실행
	    person = search_queue.popleft()
        if not person in searched:
		    if person_is_seller(person):
		        print person + " is a mango seller!"
        		return True
		    else:
		        search_queue += graph[serson] ## 망고 판매상이 아니라면, 그 사람의 이웃들을 큐에 추가
                searched.append(person)
	return False ## 여기까지 도달했다면 망고 판매상이 아무도 없음을 뜻함
 
def person_is_seller(name):
    return name[-1] == 'm' ## 사람 이름이 m으로 끝난다면 망고 판매상이라고 판단

너비 우선 탐색 알고리즘이 종료되는 경우

• 대상을 찾은 경우
• 대상이 존재하지 않는 경우

확인한 사람을 추적하는 이유?

• 그렇지 않으면 무한반복이 일어날 수 있음
• 예 : 한 친구가 여러 다른 친구의 친구인 경우, 그 친구는 큐에 두 번 들어가게 된다 (peggy처럼). 서로 참조하는 관계에 있을 때 서로가 서로를 큐에 추가하며 무한반복에 빠지게 됨.

너비 탐색 알고리즘의 실행시간

• 너비 탐색 알고리즘 = 그래프의 모든 정점을 따라 움직임.

  • 따라서 실행 시간은 최소한 O(간선의 갯수).

• 큐에 탐색할 사람을 추가하는 데에는 상수 시간인 O(1)이 걸림.

  • 모든 사람에 대해서는 O(사람의 수)이 걸림

• 결론 : 너비 우선 탐색은 O(사람의 수 + 간선의 수) 의 실행시간을 가짐

  • 보통 O(V+E)라고 표기
  • V = 정점의 수
  • E = 간선의 수