2023.09.17 Today's Challenge

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

LeetCode - The World's Leading Online Programming Learning Platform

비트마스크와 BFS를 활용해 풀면 된다고 한다.

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        qu = deque([(1<<i, i, 0) for i in range(n)])
        visited = set((1<<i, i) for i in range(n))

        while qu:
            mask, node, dist = qu.popleft()
            if mask == (1<<n) - 1:
                return dist
            for nei in graph[node]:
                new_mask = mask | (1 << nei)
                if (new_mask, nei) not in visited:
                    visited.add((new_mask, nei))
                    qu.append((new_mask, nei, dist+1))