BFS를 사용하는 스네이크 래더

기본적으로 문제는 다음 코드 블록에 있습니다.

    queue.append(src)
    distanceDict[src] = 0
    visited = set()
    while (len(queue) > 0):
        curr = queue.pop(0)
        visited.add(curr)

        for vertex in self.vertList[curr]:
            if vertex not in visited:
                queue.append(vertex)
                distanceDict[vertex] = distanceDict[curr] + 1

다음 기본 그래프로 동일하게 설명하려고합니다.

아래 그래프 에서 꼭지점에서 꼭지점 1까지 의 최단 경로를 찾아야한다고 가정 3합니다. 위의 구현을 사용하면 다음과 같은 반복 작업이 수행됩니다.

1. 1Queue에 정점 을 추가 Q하고 거리를0
2. 다음으로, 당신은 팝업 1에서 Q에서 while루프 및 방문으로 표시
3. 다음으로 모든 이웃을 방문하여 대기열에 추가합니다 Q.

따라서이 시점에서 다른 개체의 상태는 다음과 같습니다.

우리는 정점이 2있고 3큐에 Q있고 distance사전은 다음과 같을 것입니다. distance[1] = 0, distance[2] = 1, distance[3] = 1그리고 이것은 우리가 아직 정점 2과 배열 3을 추가하지 않았기 때문에 문제 visited가 시작되는 곳입니다. 우리가 방문하면 다음 반복에서이 정점의 거리를 다시 업데이트하기 시작할 것입니다. 다른 이웃들로부터 다시.

4. 다시 알고리즘으로 돌아가서 이제 다시 while루프 의 시작 과 여기에서 pop정점 2으로 이동하여 방문한 것으로 표시합니다.
5. 다음에 방문하지 않은 이웃을 살펴볼 3때 우리는 이미 방문한 것을 다시 방문하고 distance잘못된 값으로 사전을 업데이트합니다 .

정점 2과 그 이웃 을 방문한 후 다른 오브젝트의 상태는 다음과 같습니다.

3큐에 정점 이 있고 거리 사전은 distance[1] = 0, distance[2] = 1, distance[3] = 2. distance[3]반복에서 본 것처럼 잘못 업데이트되었습니다.

그러나 수정은 우리가 다른 이웃을 통해 큐에 다시 넣지 않도록 정점을 방문한 직후 방문한 것으로 표시해야하는 매우 간단합니다.

지금 쯤이면 BFS 함수에 대한 올바른 구현이 주어진 것과 같아야한다고 이미 짐작했을 것입니다.

from collections import defaultdict

global INT_MAX
INT_MAX = 3 ** 38


class Graph:
    def __init__(self):
        self.vertList = defaultdict(list)

    def addEdge(self, u, v):
        self.vertList[u].append(v)

    def distanceBFS(self, src, target):
        queue = []
        queue.append(src)
        distanceDict = {}
        for v in self.vertList:
            distanceDict[v] = INT_MAX
        distanceDict[src] = 0
        visited = set()
        visited.add(src)
        while (len(queue) > 0):
            curr = queue.pop(0)

            for vertex in self.vertList[curr]:
                if vertex not in visited:
                    queue.append(vertex)
                    visited.add(vertex)
                    distanceDict[vertex] = distanceDict[curr] + 1

        print(distanceDict[target])



    def solveSnakesLadder(self):
        snakeLadderDict = {2: 13, 5: 2, 9: 18, 18: 11, 17: -13, 20: -14, 24: -8, 25: 10, 32: -2, 34: -22}
        # we have 36 boxes --> i
        # we can throw a dice at each of these 36 boxes and it can be from 1 to 6
        # j is new position on the board after throwing a dice
        for i in range(0, 37):
            for dice in range(1, 7):
                j = i + dice
                if j in snakeLadderDict:
                    j += snakeLadderDict[j]
                if j <= 36:
                    self.addEdge(i, j)
        self.distanceBFS(0, 36)


g = Graph()
g.solveSnakesLadder()