[Algorithm] LeetCode - Clone Graph

📠 문제

• Clone Graph
• 난이도: Medium
• 주어진 그래프를 깊은 복사하는 문제이다.

class Node {
    public int val;
    public List<Node> neighbors;
}

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

💡 풀이

어어...? 이 문제를 풀면서 살짝 당황했다. 당연히 쉽게 생각했던 깊은 복사가 생각보다 쉽지 않구나라는 것을 알게 되었다. 왜냐하면 새로운 객체를 생성하면서 연결된 객체들을 다시 연결해줘야 하기 때문에 이것이 생각보다 까다롭다.

 

문제에서 가지고 있는 val을 key로 사용하고 새롭게 인스턴스를 만들면 된다. 만약 val이 없다면 Swift는 ObjectIdentifier를 활용하면 된다. 나는 mapped라는 딕셔너리를 활용하여 객체에 바로 접근하고 그 객체에 연결된 객체를 새로운 객체를 만들어서 연결해주었다. 연결된 객체를 방문하는 방식은 BFS를 사용했다.

class Solution {
    func cloneGraph(_ node: Node?) -> Node? {
        guard let node else { return nil }
        
        let copied = Node(node.val)
        var mapped: [Int: Node] = [node.val: copied]

        var queue = [node]
        var i = 0

        while queue.count > i {
            let popped = queue[i]
            let neighbors = popped.neighbors.compactMap { $0 }

            neighbors.forEach { node in
                let value = node.val
                
                if mapped[value] == nil {
                    mapped[value] = Node(value)
                    queue.append(node)
                }

                mapped[popped.val]?.neighbors.append(mapped[value])
            }

            i += 1
        }

        return copied
    }
}

결과는 아래와 같았다.