25. 그래프(Graph) - 최단 경로 찾기

너비 우선 검색(bfs)의 응용입니다. 

 

경로의 길이가 1인 노드(정점)들을 찾아보고,
길이가 2인 노드들을 찾아보고...
반복하다 목표를 찾으면 끝입니다. 

 

각 노드를 처음 방문했을 때 
직전 노드와 현 노드를 기록하는데 
이것이 최단 경로의 재료가 됩니다.

 

이 기록을 도착 노드에서 시작 노드까지
역으로 거슬러 올라가면
최단 경로가 되기 때문입니다. 

 

이 재료를 중간중간 저장할 수 있도록
set이었던 marked를 딕셔너리로 수정합니다. 

class Graph:
    def __init__(self):
        self.graph = {}

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

    def show(self):
        for node in self.graph:
            print(node, '-', self.graph[node])

    def bfs(self, start, finish):
        queue = [start]
        marked = {start: None}
        while queue:
            v = queue.pop(0)
            if v == finish:
                return marked
            for w in self.graph[v]:
                if w not in marked:
                    marked[w] = v  # 직전 노드(v)와 현재 노드(w)를 기록합니다.
                    queue.append(w)

    def shortest_path(self, start, finish):
        marked = self.bfs(start, finish)
        if finish not in marked:
            return False
        # 역으로 거슬러 올라갑니다.
        path = []
        node = finish
        while node != start:
            path.append(node)
            node = marked[node]
        path.append(start)
        return path[::-1]  # 보기 좋게 뒤집어 줍니다.


g = Graph()
g.add(0, 1)
g.add(0, 2)
g.add(0, 4)
g.add(1, 2)
g.add(2, 3)
g.add(2, 4)
g.add(3, 4)
g.show()
print(g.shortest_path(0, 3))

0 - {1, 2, 4}
1 - {0, 2}
2 - {0, 1, 3, 4}
4 - {0, 2, 3}
3 - {2, 4}
[0, 2, 3]

직전 노드와 현 정점을 기록하는 다음 코드가 핵심입니다. 

self.marked[w] = v

너비 우선 탐색으로 최단 경로를 찾았기 때문에
처음 방문했을 때 남긴 기록들을
역으로 거슬러 올라가기만 해도
최단 경로가 나옵니다. 

거꾸로 올라갔기 때문에 경로가 역순으로 보입니다.
path[::-1]로 reverse 해줍니다. 

그림을 그려보면 쉬워집니다.

0 - {1, 2, 4}
1 - {0, 2}
2 - {0, 1, 3, 4}
4 - {0, 2, 3}
3 - {2, 4}

 

큐에 0이 들어 있는 상태에서 시작합니다. 

 

큐에서 0을 꺼냄.  
그래프의 0에 들어있는 {1,2,4}를 하나씩 꺼냄. 
마크에 있는 지 확인..
모두 미방문이므로 마크에 {1:0, 2:0, 4:0}을 남기고 모두 큐에 넣음. 

 

큐에서 1을 꺼내서 그래프의 1에 들어 있는 {0, 2}를 하나씩 마크에 있는지 확인. 다 있네요. 

 

큐에서 2를 꺼내서 그래프의 2에 들어 있는 {0, 1, 3, 4}를 마크에 있는지 확인. 3이 없습니다.
3을 큐에 추가하고, {3: 2}를 마크에 기록.

 

큐에서 4을 꺼내서 그래프의 4에 들어 있는 {0, 2, 3}를 하나씩 마크에 있는지 확인. 다 있네요. 

 

큐에서 3을 꺼내서 목표인 것을 확인... 

 

이제 경로를 역추적합니다. 
3은 2에서, 2는 0에서 온 경로를 찾을 수 있고.. 
이걸 거꾸로 돌리면 완료...