Leetcode 133. Clone Graph

문제 링크

https://leetcode.com/problems/clone-graph/?envType=study-plan-v2&envId=top-interview-150

문제 해석

• 연결된 무방향 그래프 제공
• Node 는 값 ( val ) 이랑 주변 인접 노드 제공하는 ( neighbors ) 로 구성
• 참조 하지 말고 , 전부 새로 생성해서 return

문제 해결

• DFS 를 이용해서 순회하자
• 배열에 생성한 Node 들을 저장하자

슈도 코드

data[Null] * 101
visited[false] * 101
stack = []
stack.push(head)
while stack!=null
	node = stack.pop()
	if data[node.val] == null
		data[node.val] = new Node(node.val)
	for (neighbor_node : node.neighbor)
		if data[neighbor_node.val] == null
			data[neighbor_node.val] = new Node(neighbor_node.val)
		data[neight_node.val].neighbor[count++] = neighbor_node
		stack.append(neighbor_node)
return data[1]

결과

사담

• BFS 를 이용해서 , 풀 생각은 바로 했으나 , stack 에 val 을 넣을지 , Node 를 넣을지 고민했으나 ,
  val 을 넣으면 neighbor 을 이중 순회 해야할 거 같아서 Node 를 넣었다.
• data 에 Node 를 넣었는데도 , Beat 88 % 인거를 보면 대부분 다 배열을 사용해서 푼 거 같다.

메모본

• 단순 구현 문제라 생략

Writed By Obisidan