[leetcode] #847. Shortest Path Visiting All Nodes

문제 설명

링크
n 개의 모든 노드를 탐색하는 가장 짧은 경로를 반환하는 문제

접근 - Bitmask, BFS

• 각 노드를 2진수의 자리로 표현
• n = 5 일때, final state = 11111(2)
• bfs 를 활용하여 (다음상태, 다음노드) 가 seen 에 없으면 queue 에 추가

# 다음상태 = 현재상태 | 1 << 다음노드
next_state = state | (1 << next_node)

코드

# https://leetcode.com/problems/shortest-path-visiting-all-nodes/
from collections import deque
class Solution:
    def shortestPathLength(self, graph: [[int]]) -> int:
        n = len(graph)

        # start from every node
        q = deque()
        seen = set()
        
        # 시작상태
        for i in range(n):
            state = 1 << i
            print(bin(state))  # 00001, 00010, 00100, 01000, 10000
            q.append((state, 0, i)) # state, cost, node
            seen.add((state, i))

        final_state = (1 << n) - 1
        print(bin(final_state)) # 11111
        while q:
            state, cost, curr = q.popleft()
 
            if state == final_state:
                return cost
            for next_node in graph[curr]:
                next_state = state | (1 << next_node)

                if (next_state, next_node) not in seen:
                    q.append((new_state, cost + 1, nei))
                    seen.add((new_state, nei))