1용어 정리

 

이 문제를 제대로 이해하려면 용어를 정리할 필요가 있습니다. 싸이월드를 예로 들었던 일촌, 친척, 촌수 개념을 좀 더 일반적인 친구 관계로 정리해 보겠습니다.

 

• 친구(일촌): 어떤 두 사람이 직접 아는 사이일 때, 즉 서로 친구 요청을 수락한 경우 친구라고 합니다.

(예) A가 B의 친구이면 B도 A의 친구입니다.

 

• 모든 친구(친척): 어떤 사람이 직접 아는 친구들과 그 친구들의 친구들, 즉 직간접으로 아는 모든 사람을 말합니다(자기 자신도 포함).

(예) A와 B가 친구이고 B와 C가 친구이고 C와 D가 친구이면(A-B-C-D), A에게는 A, B, C, D 전부가 ‘모든 친구’입니다.

 

• 친밀도(촌수): 어떤 사람 두 명이 서로 직간접으로 아는 사이일 때 두 명이 서로 몇 단계를 거쳐 아는지 나타내는 숫자입니다(자기 자신의 친밀도는 0).

(예) A와 B가 친구이고 B와 C가 친구이고 C와 D가 친구이면(A-B-C-D), A와 B의 친밀도는 1, A와 C의 친밀도는 2, A와 D의 친밀도는 3입니다.

 

용어 정의를 이용해서 우리가 풀어야 할 문제를 다시 적어 보면 다음과 같습니다.

 

친구 관계를 이용하여 어떤 한 사람의 ‘모든 친구’를 출력하는 알고리즘을 만들어 보세요.

 

이제 이 문제를 푸는 데 꼭 필요한 자료 구조인 ‘그래프(graph)’를 알아볼 차례입니다.