<p>You have an undirected, connected graph of <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>. You are given an array <code>graph</code> where <code>graph[i]</code> is a list of all the nodes connected with node <code>i</code> by an edge.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest1-graph.jpg" style="width: 222px; height: 183px;" />
<pre>
<strong>Input:</strong> graph = [[1,2,3],[0],[0],[0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [1,0,2,0,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest2-graph.jpg" style="width: 382px; height: 222px;" />
<pre>
<strong>Input:</strong> graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible path is [0,1,4,2,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>1 &lt;= n &lt;= 12</code></li>
	<li><code>0 &lt;= graph[i].length &lt;&nbsp;n</code></li>
	<li><code>graph[i]</code> does not contain <code>i</code>.</li>
	<li>If <code>graph[a]</code> contains <code>b</code>, then <code>graph[b]</code> contains <code>a</code>.</li>
	<li>The input graph is always connected.</li>
</ul>

class Solution:
    def shortestPathLength(self, graph):
        length = len(graph) # 그래프의 노드 개수를 length에 저장
        result = 0 # BFS의 각 레벨(탐색 단계)에서 거리를 추적하는 변수 result를 초기화
        visited_node = [] # 각 노드의 방문 상태를 추적할 리스트 visited_node를 초기화
        queue = [] # BFS를 수행하기 위한 큐 queue를 초기화, 큐는 각 노드와 그 노드까지의 방문 상태(비트마스크)를 저장

        for i in range(length): # 모든 노드에서 탐색을 시작하기 위해 초기 상태를 설정
            visited_node.append(set([1<<i])) # 1<<i는 노드 i에 해당하는 비트를 1로 설정한 비트마스크, 각 노드 i를 방문한 상태로 초기화된 비트마스크를 visited_node에 추가
            queue.append([i, 1<<i]) # 각 노드와 초기 비트마스크를 큐에 추가하여 BFS 탐색을 시작, i는 현재 노드의 인덱스, 1<<i는 현재 노드를 방문한 상태를 나타내는 비트마스크

        while queue: # 큐가 비어 있지 않은 한, 탐색을 계속 진행
            result = result + 1 # 현재 레벨의 탐색이 끝날 때마다 result를 증가시켜 경로의 길이를 추적
            new_queue = [] # 현재 레벨에서 탐색한 결과를 저장할 새로운 큐 new_queue를 초기화

            for node, value in queue: # 현재 큐에서 각 노드와 그 노드의 방문 상태(비트마스크)를 가져와 탐색을 시작
                for neigbour_node in graph[node]: # 현재 노드의 모든 이웃 노드를 순회, 각 이웃 노드를 대상으로 탐색을 진행
                    # 이웃 노드를 방문한 후의 새로운 비트마스크 mid_node를 계산
                    mid_node = (1<<neigbour_node)|value # 이는 현재 비트마스크 value에 이웃 노드 neigbour_node를 방문했음을 나타내는 비트를 추가한 결과
                    """
                    | (비트 OR 연산자)
                        •	|는 비트 OR 연산자로, 두 숫자의 대응하는 비트가 하나라도 1이면 그 결과 비트가 1이 되는 연산을 수행
                        •	예를 들어, value가 0101(5)이고 1 << neigbour_node가 1000(8)이라면, 이 둘을 OR 연산하면 1101이 됨. 이 값은 10진수로 13에 해당.
                        •	이 연산은 새로운 노드를 방문한 상태를 현재 방문 상태(value)에 추가하는 역할을 함
                    """
                    if mid_node not in visited_node[neigbour_node]: # 새로운 비트마스크 mid_node가 이웃 노드 neigbour_node에서 아직 방문되지 않았다면, 그 노드를 탐색할 필요가 있음
                        if mid_node+1 == 1<<length: # 만약 모든 노드를 방문한 비트마스크 mid_node가 완성되었다면(즉, 1<<length는 모든 비트를 1로 설정한 비트마스크), 
                            return result # 탐색을 종료하고 result를 반환

                        visited_node[neigbour_node].add(mid_node) # 현재 이웃 노드 neigbour_node의 새로운 비트마스크 mid_node를 visited_node에 추가하여 이 상태를 기록
                        new_queue.append([neigbour_node, mid_node]) # 새로운 상태(이웃 노드 neigbour_node와 비트마스크 mid_node)를 다음 레벨의 큐 new_queue에 추가하여 탐색을 계속

            queue = new_queue # 현재 레벨의 탐색이 끝나면, 새로 생성된 큐 new_queue를 현재 큐 queue로 업데이트하여 다음 레벨의 탐색을 준비
        return 0 # 만약 BFS 탐색이 종료될 때까지 모든 노드를 방문할 수 없다면, 0을 반환
    
    """
    알고리즘 개요

	1.	**BFS (너비 우선 탐색)**를 사용하여 각 노드에서 출발하여 모든 노드를 방문하는 경로를 탐색합니다.
	2.	비트마스크를 사용하여 각 상태(특정 노드를 방문한 상태)를 표현합니다.
	3.	각 노드에 대해 초기 상태를 설정하고, 이를 큐에 추가하여 BFS를 시작합니다.
	4.	각 노드에서 가능한 모든 이웃 노드로 이동하며, 방문 상태를 갱신합니다.
	5.	모든 노드를 방문한 상태에 도달했을 때, BFS의 현재 깊이를 반환합니다.

    비트마스크의 역할

    비트마스크는 그래프의 노드 방문 상태를 효율적으로 추적하는 데 사용됩니다. 예를 들어, 그래프에 4개의 노드가 있다면, 비트마스크 0001은 첫 번째 노드만 방문한 상태를, 1111은 모든 노드를 방문한 상태를 나타냅니다.

    예제:

        •	노드 방문 상태를 비트마스크로 표현:
        •	그래프에 노드가 4개 있다고 가정하면, 4비트로 각 노드의 방문 상태를 표현할 수 있습니다.
        •	0001: 노드 0만 방문
        •	0011: 노드 0과 1을 방문
        •	1111: 모든 노드를 방문
        •	1 << i 연산:
        •	1 << i는 1을 i만큼 왼쪽으로 이동시켜, 노드 i에 해당하는 비트만 1로 만드는 연산입니다.
        •	예를 들어, i = 2라면 1 << 2는 0100이 됩니다.
        •	이를 통해 특정 노드를 방문한 상태를 나타낼 수 있습니다.
        •	| (비트 OR 연산자):
        •	| 연산은 두 비트마스크를 합쳐 새로운 상태를 만듭니다. 예를 들어:
        •	value = 0101 (노드 0과 2를 방문)
        •	1 << 3 = 1000 (노드 3을 방문하려고 함)
        •	0101 | 1000 = 1101 (노드 0, 2, 3을 방문한 상태)

    알고리즘의 흐름

        1.	초기화:
        •	length: 그래프의 노드 수.
        •	result: 현재 BFS 레벨을 나타내며, 경로의 길이를 추적.
        •	visited_node: 각 노드의 방문 상태를 기록할 리스트. 각 노드는 비트마스크를 사용하여 방문 상태를 관리.
        •	queue: BFS를 수행하기 위한 큐. 이 큐에는 현재 노드와 그 노드까지의 방문 상태가 들어 있습니다.
        2.	모든 노드에서 BFS를 시작:
        •	각 노드에 대해 1 << i를 사용하여 해당 노드를 방문한 상태로 초기화하고, 이를 visited_node와 queue에 추가합니다.
        3.	BFS 탐색:
        •	큐에서 노드를 꺼내고, 해당 노드의 모든 이웃 노드를 탐색합니다.
        •	이웃 노드로 이동할 때, 현재 상태에 이웃 노드를 방문했다는 정보를 추가하여 새로운 비트마스크를 생성합니다 (mid_node).
        •	이 새로운 상태가 이전에 방문된 적이 없다면 큐에 추가하고, 모든 노드를 방문한 상태인지 확인합니다.
        4.	모든 노드를 방문하면 종료:
        •	모든 노드를 방문한 상태 (mid_node + 1 == 1 << length)에 도달하면, 현재 BFS의 깊이(result)를 반환합니다.
        5.	모든 경우를 탐색해도 모든 노드를 방문하지 못하면 0을 반환:
        •	이 경우는 이론적으로 발생하지 않습니다. 그래프가 연결되어 있다고 가정하면, BFS를 통해 반드시 모든 노드를 방문할 수 있기 때문입니다.

    비트마스크의 핵심 역할

        •	효율적인 상태 추적: 비트마스크를 사용하면 각 노드에서의 방문 상태를 간단한 정수 연산으로 추적할 수 있습니다.
        •	중복 방문 방지: visited_node 리스트를 통해 이미 방문한 상태를 기록하고, 중복 탐색을 방지합니다.

    이렇게 비트마스크를 활용함으로써, 이 문제는 매우 효율적으로 해결될 수 있습니다.
    """
19600