leetcode hard : Shortest Path Visiting All Nodes

Shortest Path Visiting All Nodes

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

풀기 전

• n이 최대 12개인걸 봐서는 대단히 기가맥힌 엄청난 optimal solution이 있다기보다는 naive approach부터 optimize해가는 방식으로 접근하는게 더 좋을듯하다.
• 일반적인 bfs로는 해결이 불가한 까다로운 부분이 있다.
  • 같은 노드 재방문 가능 → visited를 일반적인 bfs 방식으로 기록하면 안됨.
    • visited를 기록하지 않을시 무한루프 발생 가능
• 일반적인 visited set은 어떤 노드에 방문했는지의 정보만을 담지만 여기에 현재 위치까지 추가하면 문제의 요구사항을 만족시킬 수 있음.
• 근데 구현은 좀 어떻게 해야될지 생각이 안난다.
• Related Topics에 bit manipulation이 있는데 이게 여기 왜 있을까

솔루션 학습

내 아이디어랑 비슷한 솔루션을 찾았다. (솔루션 링크)

bit manipulation은 방문한 노드를 bitmask로 표현하는데에 쓰이는거같다.

파이썬 버전

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        queue = deque()
        status = set()

        for i in range(len(graph)):
            mask = 1 << i
            status.add( (mask, i) )
            queue.append( (mask, i, 0) )

        while queue:
            cur = queue.popleft()

            if cur[0] == (1 << len(graph)) - 1:
                return cur[2]
            else:
                for v in graph[cur[1]]:
                    new_mask = cur[0] | (1 << v)
                    new_status = (new_mask, v)
                    if new_status not in status:
                        queue.append( (new_mask, v, cur[2]+1) )
                        status.add(new_status)

• queue는 bfs를 위한 큐
• status는 방문한 노드뿐만 아니라 현재 위치까지 포함하는 visited set이다.
• shortest path length를 찾기 위해 모든 노드에서 동시에 출발한다.
  • 그냥 초기 queue에 모든 노드를 담기만 하면 된다.
• 초기화
  • 모든 노드를 추가한다.
  • status에 현재 노드만 1인 mask와 현재 노드를 튜플로 묶어서 추가한다.
  • 큐에 현재 상태 + path length를 추가한다.
• BFS
  • mask가 모두 1이면 (모두 방문했으면) path length를 리턴한다.
    • bfs라서 무조건 shortest임이 보장된다.
  • 현재 노드의 이웃 노드들에 대해
    • 해당 노드에 방문했을 때의 새 마스크와 새 상태를 만들고
    • 새 상태가 이미 visted가 아니면 queue와 status에 추가한다.

복잡도 분석

일반적인 BFS는 같은노드 재방문이 불가하여 모든 정점과 모든 간선을 한 번씩만 체크하게 된다.

따라서 인접행렬인 경우 O(V^2)이고 인접리스트인 경우는 O(V + E)이다.

하지만 이 문제는 같은노드 재방문이 가능하기 때문에 모든 정점과 간선이 중복 체크될 수 있고

탐색의 복잡도가 exponential해진다. (상태값을 이용해 pruning을 하긴 하지만 exponential한 전체 탐색 트리에서 pruning을 한거기 때문에 결국 exponential하다.)

즉 한 노드에서 출발하는 BFS의 복잡도가 O(2^N)이다.

하지만 우리는 N개의 노드에서 동시에 출발하고 있다. 따라서 O(N * 2^N)이다.

시간복잡도와 공간복잡도 모두.