[leetcode] 847. Shortest Path Visiting All Nodes

leetcode.com/problems/shortest-path-visiting-all-nodes/

Shortest Path Visiting All Nodes - LeetCode

문제

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

모든 노드를 방문하는 최단경로(중복방문 허용)를 구하는 문제이다.

풀이

Bitmasking을 이용하면 쉽게 풀 수 있다.

Bitmasking이란, 경로를 이진수로 표현하는 것인데,예를 들어, A,B,C라는 정점들이 있을 때 A는 100, B는 010, C는 011표현이 된다. 만약 BC 또는 CB라는 경로를 지나왔다면 비트마스킹으로는 011로 표현될 것이다.

방문한 경로를 history라는 set에 저장을 할 것인데, 이때 BitMasking은 경로의 순서에 관한 정보는 담고 있지 않으므로, 마지막에 방문한 노드를 추가하여 (경로,마지막에 방문한 정점) 형식으로 추가해 준다. 위와 같은 방식으로 추가를 하는 이유는, 사이클이 생기는 경우를 막기 위함이다.

 

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:

        if len(graph) == 1:
            return 0

        history = set()
        num_nodes = len(graph)
        queue = [(1 << i, i, 0) for i in range(num_nodes)]
        destination = (1 << len(graph)) - 1

        while len(queue) > 0:
            current_path, current_node, steps = queue.pop(0)
            for v in graph[current_node]:
                next_path = current_path | (1 << v)
                if next_path == destination:
                    return steps + 1
                if (next_path, v) not in history:
                    history.add((next_path, v))
                    queue.append((next_path, v, steps + 1))