5모든 친구 찾기 알고리즘

 

주어진 친구 관계 그래프에서 Tom의 모든 친구를 출력하는 것은 매우 간단합니다. 일단 Tom 자신을 출력합니다. 그리고 fr_info 딕셔너리의 키 Tom의 값에 Jerry가 있으므로 Jerry를 출력합니다. 다시 Jerry의 친구를 찾아보니 Tom 한 명뿐입니다. Tom은 이미 자기 자신을 출력했으므로 알고리즘을 종료합니다.

그렇다면 Summer의 모든 친구를 출력하는 것은 어떨까요? 일단 Summer 자신을 출력합니다. 다음으로 Summer의 친구들을 찾아보니 세 명이 있습니다. 세 명의 이름을 출력하고 다시 이 세 명의 친구들을 따라가 봐야 합니다. 이처럼 친구가 여러 명이고 그 친구들의 친구가 또 여러 명일 때는 기억력만으로는 모든 친구를 따라가기에는 무리가 있습니다. 기억력만 가지고 뭔가를 하기 어렵다면 메모를 하면 좋겠지요?

잘 생각해 보면 이 문제를 풀기 위해 두 가지 메모가 필요합니다.

첫째, 앞으로 처리해야 할 사람들입니다. 꼬리에 꼬리를 무는 친구의 친구들을 한 명도 빠뜨리지 않고 처리하려면 친구의 이름이 나올 때마다 메모지에 적어 두었다가 한 명씩 처리하면서 메모지에서 지워야 합니다.

둘째, 이미 추가된 사람들입니다. 친구 추적 과정에서 한 명이 여러 번 나오거나 추적이 무한 반복되지 않게 하려면 이미 처리 대상으로 올린 사람은 중복되지 않도록 메모지에 적어 두어야 합니다.

앞에서 살펴본 Tom과 Jerry에서 두 번째 과정을 하지 않는다면 어떻게 될까요? Tom은 Jerry를 친구로 출력하고, Jerry는 다시 Tom을 친구로 출력하고, 다시 Tom은 Jerry를 친구로 출력하는 과정이 영원히 반복될 위험성이 있습니다.

우리가 만들 알고리즘에서는 ‘앞으로 처리해야 할 사람을 넣어 두었다가 하나씩 꺼내기 위한 기억 장소’로 큐(변수 이름: qu)를 이용합니다. 또한 ‘이미 처리 대상으로 추가한 사람들을 적어 둘 기억 장소’로 집합(변수 이름: done)을 이용해 보겠습니다.