UNIT 13 (자료 구조)

친구의 친구 찾기 (그래프)

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

#친구 리스트에서 자신의 모든 친구를 찾는 알고리즘
#입력 : 친구 관계 그래프 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: #아직 done 큐에 추가된 적 없는 사람을
                qu.append(x) #큐에 추가
                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")

문제) 모든 친구를 찾아서 친밀도를 계산하는 알고리즘을 만들어라

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

def print_all_friends(g, start):
    qu = []
    done = set()
    qu.append((start, 0))

    done.add(start)

    while qu:
        (p, d) = qu.pop(0)
        print(p, d)
        for x in g[p]:
            if x not in done:
                qu.append((x, d + 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")

연습문제)

13-1 Unit 13에서 배운 그래프 탐색 알고리즘을 이용하여 다음 그래프를 탐색하는 프로그램을 만들어라. (시작 꼭짓점 : 1)

def print_all_friends(g, start):
    qu = []
    done = set()

    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)

fr_info = {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}

print_all_friends(fr_info, 1)

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

qu와 done에 1추가 -> p=1 -> 1의 value가 done에 존재하지 않으면 qu와 done에 추가 ...
q[1], done[1]
q[], done[1] -> qu.pop(0), p=1
print(1)
q[2], done[1,2]
q[2,3], done[1,2,3]
q[3], done[1,2,3] -> qu.pop(0), p=2
print(2)
q[3,4], done[1,2,3,4]
q[3,4,5], done[1,2,3,4,5]
q[4,5], done[1,2,3,4,5] -> qu.pop(0), p=3
print(3)
q[5], done[1,2,3,4,5] -> qu.pop(0), p=4
print(4)
q[], done[1,2,3,4,5] -> qu.pop(0), p=5
print(5)

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10