[ALGORITHMS]문제 15 친구의 친구 찾기(그래프)

문제 15

친구의 친구 찾기

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

1. 용어 정리

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

ex)A가 B의 친구이면 B도 A의 친구입니다

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

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

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

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

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

이 문제를 푸는 데 꼭 필요한 자료 구조인 '그래프'를 알아볼 차례입니다'

2. 그래프

위의 그림과 같이 꼭지점(동그라미로 표현) 여러 개와 각 꼭짓점 사이의 연결관계를 선으로 표현한 것을 그래프라고 합니다. 그림 15-2는 1부터 6 까지 이름이 붙여진 꼭짓점(vertex)이 여섯개 있고, 그 꼭지점 사이를 연결하는 선 (edge)이 일곱 개 있습니다.

3. 그래프로 친구 관계 표현하기

예를 들어 사람이 여덟명 있고, 친구 관계가 다음과 같을 때 이 친구관계를 그래프로 어떻게 표현할 수 있을까요?

- Summer와 John은 서로 친구입니다.

- Summer와 Justin은 서로 친구입니다.

- Summer와 Mike는 서로 친구입니다.

- Justin과 May는 서로 친구입니다

- May와 Kim은 서로 친구입니다.

- John과 Justin은 서로 친구입니다.

- Justin과 Mike는 서로 친구입니다.

- Tom과 Jerry는 서로 친구입니다.

문장으로 설명한 친구 관계를 그래프를 사용하여 수학적인 관계로 표현하였습니다.

이제 이 그래프를 파이썬 프로그램으로 만들어 볼 차례입니다.

4. 파이썬으로 그래프 표현하기

파이썬에서 그래프를 자료 구조로 만들어 저장하는 방법에는 여러 가지가 있지만

여기서는 우리가 이미 알고 있는 리스트와 딕셔너리를 이용해서 그래프를 표현하는 방법을 살펴 보겠습니다.

일단 그래프를 표현하려면 각 꼭지점의 정보부터 저장해야합니다. 그래프를 표현할 fr_info 딕셔너리를 만들고 키(key)로 각 꼭짓점을 지정합니다.

여기 까지를 파이썬 프로그램으로 표현하면 다음과 같습니다

안타깝지만 이 프로그램은 실행 되지않습니다 . 딕셔너리에는 키와 키에 대응하는 값(value)이 필요하기 때문입니다.

따라서 꼭지점과 더불어 필요한 선을 fr_info의 키에 대응하는 값으로 적어주겠습니다

완성된 친구 정보 그래프 프로그램은 다음과 같습니다

참고로 A가 B의 친구면 B는 자동으로 A의 친구입니다. 따라서 Summer에 대응한느 리스트에 John이 있으면 John에 대응하는 리스트에도 자연히 Summer가 있는 것입니다.

5. 모든 친구 찾기 알고리즘

주어진 친구 관계 그래프에서 Tom의 모든 친구를 출력하는 것은 매우 간단합니다.

일단 Tom 자신을 출력합니다. 그리고 fr_info 딕셔너리의 키 Tom의 값에 Jerry가 있으므로 Jerry를 출력합니다. 다시 Jerry의 친구를 찾아보니 Tom 한명뿐입니다. Tom은 이미 자기 자신을 출력했으므로 알고리즘을 종료합니다.

그렇다면 Summer의 모든 친구를 출력해보겠습니다

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

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

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

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

앞에서 살펴본 Tom과 Jerry에서 두번째 과정을 하지 않는다면 무한루프에 빠질수 있습니다.(Tom에서 Jerry를 Jerry에서 Tom을 무한히 호출합니다)

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

알고리즘을 적어봅니다

1. 앞으로 처리할 사람을 저장할 큐(qu)를 만듭니다.

2. 이미 큐에 추가한 사람을 저장할 집합(done)를 만듭니다.

3. 검색의 출발점이 될 사람을 큐와 집합에 추가합니다.

4. 큐에 사람이 남아있다면 큐에서 처리할 사람을 꺼냅니다

5. 꺼낸 사람을 출력합니다

6. 꺼낸 사람의 친구들 중 아직 큐에 추가된 적이 없는 사람을 골라 큐와 집합에 추가합니다.

7. 큐에 처리할 사람이 남아있다면 4번 과정부터 반복합니다

*모든 친구를 찾는 알고리즘

이제 여기다 친밀도 계산 기능까지 넣어보겠습니다.

6. 친밀도 계산 알고리즘

예를 들어 A와 B가 친구이고 B와 C가 친구라고 가정해 봅시다 (A-B-C)

A를 기준으로 B의 친밀도는 1, B를 기준으로 C의 친밀도는 1입니다.

한편 A와 C는 B를 통해 친구의 친구가 되었으므로 A를 기준으로 C의 친밀도는 2라는 것을 쉽게 알 수 있습니다. 일반적으로 A라는 사람과 X라는 사람의 친밀도가 n이라고 하면 X의 친구 Y는 A와 친밀도가 n+1이 됩니다.

이 성질을 이용하여 어떤 사람의 친구들을 큐에 넣을때 친밀도를 1씩 증가시키면 됩니다.

*모든 친구를 찾아서 친밀도를 계산하는 알고리즘

*연습문제 

15-1 문제 15에서 배운 그래프 탐색 알고리즘을 이용하여 다음 그래프를 탐색하는 프로그램을 만들어보세요(시작 꼭짓점 : 1)

15-2 연습문제 15-1에서 만든 프로그램이 그래프를 탐색해 가는 과정을 단계별로 적어보세요

읽어주셔서 감사합니다