너비우선탐색과 그 활용법

알고리즘이란? 수업에서는 팩맨을 미로 속에서 원하는 지점까지 움직였습니다. 여기서 시작할 때, 목표 지점이 자신과 0 발자국만큼 떨어져 있다고 했습니다. 그런 다음, 목표 지점에서 한 단계 멀리 있는 모든 사각형을 찾습니다. 그다음은 목표 지점에서 두 발자국 멀리 있는 모든 사각형, 그리고 그다음은 세 발자국... 이 과정을 맨 처음에 팩맨이 출발한 사각형에 이를 때까지 계속합니다. 만일 $k+1$‍ 거리에 있는 곳에 다다르기 위해 지금까지 지나온 거리 $k$‍의 경로를 기록했다면, 팩맨에서 목표 지점에 이르기까지의 경로를 찾을 때 이를 역추적하면 됩니다.

아래는 경로 찾기 수업에서 봤던 그림입니다:

위 그래프가 무방향 그래프라는 것을 배웠었습니다. 각 정점은 벽의 일부분이 아닌 사각형에 대응하며 각 변은 이웃한 사각형을 이어줍니다.

위 과정에서 발견한 경로는 한 가지 중요한 특성이 있습니다. 팩맨에서 목표 지점까지 더 적은 수의 사각형을 거쳐서 갈 수 있는 경로는 없다는 것입니다. 이는 경로를 찾기 위해 너비우선탐색으로 알려진 알고리즘을 이용했기 때문입니다. 너비우선탐색(Breadth-first Search)은 BFS라고도 쓰며, 주어진 소스 정점에서 다른 모든 정점에 이르기까지 거치는 변의 수를 계산해 가장 짧은 경로를 찾습니다.

너비우선탐색의 또 다른 예가 있습니다: "케빈 베이컨의 6단계" 게임입니다. 이 게임의 규칙은 케빈 베이컨과 영화에 출연한 배우를 연결하고, 서로 같은 영화에 출연한 배우를 연결하는 것입니다. 연결고리가 짧을수록 더 좋은데, 6번이나 그 이하의 연결고리로 수많은 영화배우가 케빈 베이컨과 연결되었다는 사실을 알게 되면 놀랄 겁니다. 호주 여배우인 케이트 벨을 예로 들어볼까요? 케이트 벨은 2006년에 내쉬 에저튼과 함께 맥베스 에 출연했습니다. 에저튼은 2003년에 로렌스 피쉬번과 함께 매트릭스 2 - 리로디드 에 출연했고 피쉬번은 2003년에 케빈 베이컨과 함께 미스틱 리버 에 출연했습니다. 그러므로 케이트 벨의 "케빈 베이컨 숫자"는 3입니다. 사실 케이트 벨의 케빈 베이컨 숫자가 3임을 알아내는 방법은 여러 가지가 있습니다. The Oracle of Bacon website 에서 영화배우들의 케빈 베이컨 숫자를 찾아보세요.

이미 알아차렸겠지만, Oracle of Bacon 웹사이트는 방향성 없는 그래프를 관리하고 있는데 여기서 각 정점은 영화배우에 해당하고 만일 두 사람이 한 영화에 나왔다면 두 정점 사이를 잇는 변이 만들어집니다. 케빈 베이컨을 나타내는 정점에서 시작하는 너비우선탐색을 통해 다른 모든 영화배우와의 가장 짧은 연결고리를 찾을 수 있습니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.