[LeetCode] 0133. 그래프 복제

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

노드의 참조가 주어지면 연결됨 방향이 없는 그래프.

반환 딥 카피 (클론) 그래프.

그래프의 각 노드에는 값(정수) 및 목록(목록[노드]) 이웃의.

클래스 노드 { 공개 int 공개 목록; 이웃;

테스트 케이스 형식:

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

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

주어진 노드는 항상 다음과 같은 첫 번째 노드가 됩니다. 발=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 = 2)의 이웃은 첫 번째 노드(val)입니다. = 1), 3번째 노드(val = 3), 3번째 노드(val = 3)의 이웃은 2번째 노드(val = 2), 4번째 노드(val = 4)의 이웃입니다. 첫 번째 노드(val = 1) 및 세 번째 노드(val = 3).

예 2:

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

예시 3:

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

제약:

그래프의 노드 수가 다음 범위 내에 있습니다. [0, 100].
1 <= Node.val <= 100
Node.val 각 노드마다 고유합니다.
그래프에는 반복되는 간선이나 자가 루프가 없습니다.
그래프는 연결되어 있으며 해당 노드부터 모든 노드를 방문할 수 있습니다.

파이썬

				
					# Node.class 노드에 대한 정의: def __init__(self, val=0, neighbor=None): self.val = val self.neighbors = neighbor if neighbor is None else [] 클래스 솔루션: def __init__(self): self.visited = {} def cloneGraph(self, node: 'Node') -> 'Node': 그렇지 않은 경우 node: return node if node in self.visited: return self.visited[node] clone_node = Node(node.val , []) self.visited[node] = node.neighbors인 경우 clone_node: clone_node.neighbors = [node.neighbors의 n에 대한 self.cloneGraph(n)] return clone_node

파이썬

관련 기사