leetcode medium : Clone Graph

https://leetcode.com/problems/clone-graph/

Clone Graph - LeetCode

그래프를 deep copy하는게 목표!
목표는 아주 간단하고 단순하다.

일단 그래프를 복사하려면 당연히 원본 그래프를 서치해야 한다.
당연하겠지 이건?

서칭하는 동시에 복사를 해야되니까 원본 그래프를 만지면서 복사본도 똑같이 만져줄 수 있어야 한다.
원본 그래프의 노드와 복사본 그래프의 노드는 노드의 value로 연결지어 추적할 수 있다.
만약 dictionary(Java에서는 Map)를 만들고 key를 노드의 value로, value를 노드로 가지게 하면
원본을 서칭하면서 복사본을 참조할 수 있을 것이다.

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return None
        
        val_to_node = {}
        
        def clone(node):
            if node.val in val_to_node:
                return
            
            val_to_node[node.val] = Node(node.val)

            for nb in node.neighbors:
                clone(nb)
                val_to_node[node.val].neighbors.append(val_to_node[nb.val])
        
        clone(node)
        return val_to_node[node.val]

알고리즘은 너무 단순하다.
clone이라는 이름의 서치함수는 인자로 전달받은 노드가 이미 복사되어 있으면 리턴된다.
아니면 노드를 복사하고 그 neighbors도 복사한다. neighbor들도 복사가 이미 되어있으면 종료조건에 걸려 아무일도 일어나지 않을거다. neighbors가 복사된 뒤에는 복사본에도 neighbors를 추가하면된다.

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return None
        vn = {}
        def clone(node):
            if node.val in vn: return
            vn[node.val] = Node(node.val)
            for nb in node.neighbors:
                clone(nb)
                vn[node.val].neighbors.append(vn[nb.val])
        clone(node)
        return vn[node.val]

정리 찍!

이런 문제는 이렇게 하고 끝내면 안된다. iterative solution으로 구현해보자.

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return None
        vn = {}
        q = deque([node])
        while q:
            n = q.popleft()
            if n.val not in vn:
                vn[n.val] = Node(n.val)
            for nb in n.neighbors:
                if nb.val not in vn:
                    q.append(nb)
                    vn[nb.val] = Node(nb.val)
                vn[n.val].neighbors.append(vn[nb.val])
        return vn[node.val]

BFS로 구현했다. stack 써서 dfs로 하는건 거의 안될거같다. 처음에 짠 솔루션을 보면 알겠지만

for nb in node.neighbors:
    clone(nb)
    vn[node.val].neighbors.append(vn[nb.val])

recursive call 후 후속작업을 하는 부분이 있다. 이런 경우는 iterative하게 구현하기가 복잡해진다.

BFS iterative 솔루션에서 주의할점은
if n.val not in vn:
vn[n.val] = Node(n.val)
for nb in n.neighbors:
if nb.val not in vn:
q.append(nb)
vn[nb.val] = Node(nb.val)

이부분이다. 잘보면 pop될때 노드 복사 로직이 하나 있고 neighbors 추가할때 노드 복사로직이 하나가 있어서 if n.val not in vn 체크 부분이 없으면 이미 복사된 노드를 또 복사해서 새로 만드는 불상사가 생길수있다. 그렇게 되면 그래프가 완전 messed up 되어버린다.

쉽고 재밌는 문제였다.