[알고리즘] 최단 경로 구하기

문제

개념

1. 시작위치를 q 넣고, depth를 -1로 초기화
2. depth를 1 증가
3. depth별로 loop를 진행 (for i in 0~size(q))
4. 해당 depth의 node를 pop
5. 목표점에 도달했는지 비교
6. 목표점에 도달 했다면 depth return
7. 목표점에 도달하지 못했다면 이동 경로에 node를 넣고 다음경로를 q에 push
8. 동일한 depth의 검사가 끝날 때까지 4~7 반복
9. 더이상 q가 없을 때까지 진행(while)

해당 방식은 알고리즘은 트리 구조에서만 가능하다.

코드

from collections import deque 

def shortest_path(graph, start, end):
    result = -1
    visited = []
    q = deque([start])
    while q:
        result += 1
        size = len(q)

        for _ in range(size):
            node = q.popleft()
            if node == end:
                return result

            visited.append(node)
            q += graph[node] - set(visited)

if __name__ == '__main__':
    graph = {
        'A': set(['B', 'C']),
        'B': set(['A', 'D', 'E']),
        'C': set(['A', 'F']),
        'D': set(['B']),
        'E': set(['B', 'F']),
        'F': set(['C', 'E'])}

    print(shortest_path(graph, 'A', 'F'))
    # 2