Clone Graph
문제
- 완전히 같은 그래프여야 하나, 같은 노드여서는 안됨.
- Node 클래스가 따로 있음
풀이
- dfs (stack 이용)
- 어차피 최대 100개이므로 미리
visited
리스트와 출력 node들을 담은 nodeList
를 생성함
nodeList = [Node(i) for i in range(101)]
로 미리 값을 초기화 해줌. (노드가 n개 일 때, 번호는 1~n+1로 생성된다고 조건에서 알려줌)
- 평범하게 dfs 탐색을 하나,
node.val
이 int 값이기 때문에 코드가 조금 난잡함
node
와 val
은 미리 만들어 뒀으니, dfs 탐색을 하면서 neighbors
만 잘 연결해주면 됨.
- 풀고 나니 단순한 dfs인데,,, Node class때문에 뇌정지 옴
def cloneGraph(self, node: 'Node') -> 'Node':
if node:
nodeList = [Node(i) for i in range(101)] #미리 Node 생성
visited = [False for _ in range(101)] # 방문 여부
visited[0] = True # place holder
visited[node.val] = True
stack = deque()
stack.append(node)
while stack:
thisNode = stack.pop()
for nextNode in thisNode.neighbors: #인접 노드 순회
nodeList[thisNode.val].neighbors.append(nodeList[nextNode.val]) # 새 그래프에 연결
if not visited[nextNode.val]:
visited[nextNode.val] = True
stack.append(nextNode) # 방문한적 없는 노드면, stack에 넣기
return nodeList[node.val] # 첫번째 노드 반환
else:
return None
결과
- dfs (stack 이용)
- 어차피 최대 100개이므로 미리
visited
리스트와 출력 node들을 담은nodeList
를 생성함 nodeList = [Node(i) for i in range(101)]
로 미리 값을 초기화 해줌. (노드가 n개 일 때, 번호는 1~n+1로 생성된다고 조건에서 알려줌)- 평범하게 dfs 탐색을 하나,
node.val
이 int 값이기 때문에 코드가 조금 난잡함 node
와val
은 미리 만들어 뒀으니, dfs 탐색을 하면서neighbors
만 잘 연결해주면 됨.- 풀고 나니 단순한 dfs인데,,, Node class때문에 뇌정지 옴
def cloneGraph(self, node: 'Node') -> 'Node':
if node:
nodeList = [Node(i) for i in range(101)] #미리 Node 생성
visited = [False for _ in range(101)] # 방문 여부
visited[0] = True # place holder
visited[node.val] = True
stack = deque()
stack.append(node)
while stack:
thisNode = stack.pop()
for nextNode in thisNode.neighbors: #인접 노드 순회
nodeList[thisNode.val].neighbors.append(nodeList[nextNode.val]) # 새 그래프에 연결
if not visited[nextNode.val]:
visited[nextNode.val] = True
stack.append(nextNode) # 방문한적 없는 노드면, stack에 넣기
return nodeList[node.val] # 첫번째 노드 반환
else:
return None
결과
굿!
Author And Source
이 문제에 관하여(Clone Graph), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@twinklesu914/Clone-Graph저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)