클론 그래프

connected 무방향 그래프에서 노드 참조가 주어집니다.

그래프의 deep copy(클론)을 반환합니다.

그래프의 각 노드에는 이웃의 값( int )과 목록( List[Node] )이 포함됩니다.

클래스 노드 {
공개 정수 값;
공개 목록 이웃;
}

테스트 사례 형식:

단순화를 위해 각 노드의 값은 노드의 인덱스(1-인덱스)와 동일합니다. 예를 들어 첫 번째 노드는 val == 1 , 두 번째 노드는 val == 2 등입니다. 그래프는 인접 목록을 사용하여 테스트 케이스에 표시됩니다.

인접 목록은 유한 그래프를 나타내는 데 사용되는 정렬되지 않은 목록 모음입니다. 각 목록은 그래프에서 노드의 이웃 집합을 설명합니다.

주어진 노드는 항상 val = 1가 있는 첫 번째 노드입니다. 복제된 그래프에 대한 참조로 지정된 노드의 복사본을 반환해야 합니다.

예 1:



입력: adjList = [[2,4],[1,3],[2,4],[1,3]]
출력: [[2,4],[1,3],[2,4],[1,3]]
설명: 그래프에는 4개의 노드가 있습니다.
첫 번째 노드(val = 1)의 이웃은 두 번째 노드(val = 2)와 네 번째 노드(val = 4)입니다.
두 번째 노드(val = 2)의 이웃은 첫 번째 노드(val = 1)와 세 번째 노드(val = 3)입니다.
3번째 노드(val = 3)의 이웃은 2번째 노드(val = 2)와 4번째 노드(val = 4)입니다.
4번째 노드(val = 4)의 이웃은 1번째 노드(val = 1)와 3번째 노드(val = 3)입니다.

예 2:



입력: adjList = [[]]
출력: [[]]
설명: 입력에 하나의 빈 목록이 포함되어 있습니다. 그래프는 val = 1인 하나의 노드로만 구성되며 이웃이 없습니다.

예 3:

입력: adjList = []
출력: []
설명: 이것은 빈 그래프이며 노드가 없습니다.

제약:

그래프의 노드 수가 [0, 100] 범위에 있습니다.

1 <= Node.val <= 100

Node.val는 각 노드에 대해 고유합니다.

그래프에 반복되는 에지와 자체 루프가 없습니다.

그래프가 연결되고 지정된 노드에서 시작하여 모든 노드를 방문할 수 있습니다.

해결책:

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        nodemap = {}
        nodemap[node.val] = Node(val = node.val)
        paths = [node]
        while len(paths) > 0:
            curr = paths.pop()
            currcopy = nodemap[curr.val]
            for nbr in curr.neighbors:
                if nbr.val not in nodemap:
                    paths.append(nbr)
                    nodemap[nbr.val] = Node(val = nbr.val)
                currcopy.neighbors.append(nodemap[nbr.val])
        return nodemap[node.val]