파이썬 그래프 알고리즘 친구의 친구 찾기 #13

파이썬 그래프 알고리즘 친구의 친구 찾기 #13

 

 

안녕하세요.

 

친구 관계를 이용해서 어떤 한 사람이 직, 간접적으로 아는 모든 친구를 출력하는 알고리즘을 공부해 보겠습니다.

 

우리가 요즘 하는 SNS들을 보면 친구 라는 개념이 있습니다.

 

A 라는 사람이 B와 친구이고, B 라는 사람이 C와 친구라면 A와 C는 직접적인 친구 사이는 아니지만 서로 B 라는 친구를 통해서 간접적으로 아는 관계가 되는거죠.

 

이런 관계를 통해서 SNS 서비스를 하는 곳 에서는 친구 추천을 하고 있습니다. 

 

여기서 이런 친구 추천을 할 수 있게 하는 알고리즘을 공부해 보겠습니다.

 

이 알고리즘을 풀기 위해서, 우리는 파이썬의 자료 구조중 하나인 그래프에 대해서 알고 있어야 합니다.

 

우리는 수학시간에 위와 같은 그래프를 많이 보았을것 입니다. 친구의 친구를 찾기 위해선 위와 같은 그래프가 아니라 꼭짓점과 그 꼭짓점 사이를 연결하는 선들의 집합이 필요 합니다.

 

아래 그림처럼 말이죠.

 

위 그림과 같이 꼭짓점과 다른 각각의 꼭짓점 사이를 연결한 선을 그래프라고 합니다.

 

위 그림에는 꼭짓점이 6개 있고, 꼭짓점 사이를 연결하는 선이 7개 있습니다.

 

각각의 꼭짓점은 사람을 뜻하며, 연결된 선은 관계를 뜻합니다.

 

자, 그럼 이젠 그래프로 친구 관계를 좀 더 명확하게 표현해 보겠습니다.

 

1. Summer와 John은 친구 관계 입니다.

2. Summer와 Justin은 친구 관계 입니다.

3. Summer와 Mike는 친구 관계 입니다.

4. Justion과 May는 친구 관계 입니다.

5. May와 Kim은 친구 관계 입니다.

6. John과 Justin은 친구 관계 입니다.

7. Justin과 Mike는 친구 관계 입니다.

8. Tom과 Jerry는 친구 관계 입니다.

 

위에서 글로 설명한 친구 관계를 그래프로 그리면 어떻게 될 까요?

 

아래와 같은 모습일 겁니다.

 

문장으로 길게 서술한 내용을 하나의 그래프로 표현해 보았습니다.

 

그럼 이젠 파이썬의 그래프로 표현해 보도록 하겠습니다.

fr_info = {
	'Summer':
    'John':
    'Justin':
    'Mike':
    'May':
    'Kim':
    'Tom':
    'Jerry':
}

이렇게 표현하면 될까요? 여기에는 키(Key)만 있지 값이 없습니다.

 

값을 넣어서 제대로 표현 해보겠습니다.

fr_info = {
	'Summer':['John','Justin','Mike']
    'John':['Summer','Justin']
    'Justin':['John','Summer','Mike','May']
    'Mike':['Summer','Justin']
    'May':['Justin','Kim']
    'Kim':['May']
    'Tom':['Jerry']
    'Jerry':['Tom']
}

이렇게 표현 할 수 있겠죠?

 

그럼 친구의 친구를 찾기 위해서는 어떻게 하면 될까요?

 

우선, 로직을 글로 정리 해보겠습니다.

 

1. 처리 할 사람을 큐(qu)를 만들어 저장 합니다.

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

3. 출발점이 될 사람을 큐와 집합에 저장 합니다.

4. 큐에 사람이 남아 있다면 큐에서 하나씩 사람을 꺼냅니다.

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

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

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

 

위에서 정리한 글을 로직으로 짜면 어떻게 될까요?

 

# 친구 리스트에서 자신의 모든 친구를 찾는 알고리즘
# 입력: 친구 관계 그래프 g, 모든 친구를 찾을 자신 start
# 출력: 모든 친구의 이름

def print_all_friends(g, start):
    qu = []       # 기억 장소1: 앞으로 처리해야 할 사람들을 큐에 저장
    done = set()  # 기억 장소2: 이미 큐에 추가한 사람들을 집합에 기록(중복 방지)

    qu.append(start)  # 자신을 큐에 넣고 시작
    done.add(start)   # 집합에도 추가

    while qu:           # 큐에 처리할 사람이 남아 있는 동안
        p = qu.pop(0)   # 큐에서 처리 대상을 한 명 꺼내
        print(p)        # 이름을 출력하고
        for x in g[p]:  # 그의 친구들 중에
            if x not in done:  # 아직 큐에 추가된 적이 없는 사람을
                qu.append(x)   # 큐에 추가하고
                done.add(x)    # 집합에도 추가

# 친구 관계 리스트
# A와 B가 친구이면
# A의 친구 리스트에도 B가 나오고, B의 친구 리스트에도 A가 나옴
fr_info = {
    'Summer': ['John', 'Justin', 'Mike'],
    'John': ['Summer', 'Justin'],
    'Justin': ['John', 'Summer', 'Mike', 'May'],
    'Mike': ['Summer', 'Justin'],
    'May': ['Justin', 'Kim'],
    'Kim': ['May'],
    'Tom': ['Jerry'],
    'Jerry': ['Tom']
}

print_all_friends(fr_info, 'Summer')
print()
print_all_friends(fr_info, 'Jerry')

위에서 작성된 소스는 꼭짓점을 탐색하는 알고리즘 이라고도 불립니다. 예전 싸이월드를 생각해보면 모든 회원의 친척을 뽑아서 촌수를 계산 했던걸 기억 하실 겁니다.

 

이번에는 촌수 계산까지 하는 소스를 작성해 보겠습니다.

 

# 친구 리스트에서 자신의 모든 친구를 찾고 친구들의 친밀도를 계산하는 알고리즘
# 입력: 친구 관계 그래프 g, 모든 친구를 찾을 자신 start
# 출력: 모든 친구의 이름과 자신과의 친밀도

def print_all_friends(g, start):
    qu = []       # 기억 장소 1: 앞으로 처리해야 할 (사람 이름, 친밀도) 튜플을 큐에 저장
    done = set()  # 기억 장소 2: 이미 큐에 추가한 사람을 집합에 기록(중복 방지)

    qu.append((start, 0))  # (사람 이름, 친밀도) 정보를 하나의 튜플로 묶어 처리(자기 자신 친밀도: 0)
    done.add(start)        # 집합에도 추가

    while qu:               # 큐에 처리할 사람이 남아 있는 동안
        (p, d) = qu.pop(0)  # 큐에서 (사람 이름, 친밀도) 정보를 p와 d로 각각 꺼냄
        print(p, d)         # 사람 이름과 친밀도를 출력
        for x in g[p]:      # 친구들 중에
            if x not in done:          # 아직 큐에 추가된 적이 없는 사람을
                qu.append((x, d + 1))  # 친밀도를 1 증가시켜 큐에 추가하고
                done.add(x)            # 집합에도 추가

fr_info = {
    'Summer': ['John', 'Justin', 'Mike'],
    'John': ['Summer', 'Justin'],
    'Justin': ['John', 'Summer', 'Mike', 'May'],
    'Mike': ['Summer', 'Justin'],
    'May': ['Justin', 'Kim'],
    'Kim': ['May'],
    'Tom': ['Jerry'],
    'Jerry': ['Tom']
}

print_all_friends(fr_info, 'Summer')
print()
print_all_friends(fr_info, 'Jerry')

친밀도라고 불러도 되겠죠? 

 

어떤가요? 재미있지 않나요? ㅎㅎ

 

오늘 내용이 괜찮았으면 추천 부탁드립니다!!

 

감사합니다. 다음 파이썬 알고리즘 로직으로 다시 돌아 오겠습니다!

 

# 파이썬으로 배우는 알고리즘 컨텐츠는 <모두의파이썬X알고리즘, 길벗>을 참고로 작성하는 포스팅 입니다. 물론 협찬은 없습니다.ㅎㅎ

https://book.naver.com/bookdb/book_detail.nhn?bid=14341699

 

by.sTricky