친구 관계를 이용하여 어떤 한 사람이 직접 또는 간접으로 아는 모든 친구를 출력하는 알고리즘을 만들어 보세요.

 

한때 큰 인기를 끌었던 싸이월드라는 SNS에는 ‘일촌 맺기’, ‘친척’, ‘촌수’라는 개념이 있었습니다. A와 B가 일촌 관계이고 B와 C가 일촌 관계이면 A와 C는 직접 아는 사이가 아니더라도 서로 이촌 관계가 되는 식입니다.

친구가 서너 명 정도라면 종이에 사람들의 관계를 적어 보는 것만으로도 촌수를 쉽게 계산할 수 있습니다. 하지만 회원 수가 천만 명이 넘는 웹사이트에서 각 회원이 수십, 수백 명씩 일촌을 맺고 있다면 뭔가 체계적인 알고리즘이 필요할 것입니다. 싸이월드 외에도 페이스북 같은 대부분의 SNS에는 친구 관계가 있으며 친구의 친구를 찾아주는 ‘친구 추천’ 기능이 있습니다. 이러한 기능 역시 이번 문제에서 배울 ‘친구의 친구 찾기’와 비슷한 알고리즘을 사용한 것입니다.