133. Clone Graph

문제

원본 노드를 깊은 복사하는 문제이다. bfs를 사용했다.

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

Solution

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        // 방문 유무 확인 및 복제 노드를 조회하는 용도
        // 값에는 복제 노드를 저장한다.
        Map<Integer, Node> visited = new HashMap<>();
        // 큐에 시작 노드를 추가
        Queue<Node> queue = new LinkedList<>();
        if(node == null) return null;
        queue.offer(node);
        // 시작 노드 방문 체크
        Node copied = new Node(node.val);
        visited.put(node.val, copied);

        while(!queue.isEmpty()) {
            Node polledOriginNode = queue.poll();

            for(Node originNeighbor : polledOriginNode.neighbors) {
                if(!visited.containsKey(originNeighbor.val)) {
                    // 방문하지 않는 노드는 복제해서 방문 체크한다.
                    Node copiedNeighbor = new Node(originNeighbor.val);
                    visited.put(originNeighbor.val, copiedNeighbor);
                    queue.offer(originNeighbor);
                }

                // 최상위 노드의 복제 노드
                Node copiedNode = visited.get(polledOriginNode.val);
                // 이웃 노드의 복제 노드
                Node copiedNeighbor = visited.get(originNeighbor.val);

                copiedNode.neighbors.add(copiedNeighbor);
            }
        }
        return copied;
    }
}

일반적인 BFS 구현에서는 방문 배열을 단순히 방문 여부 확인 용도로 사용하지만, 이 문제에서는 방문 여부 확인 외에도 방문한 노드의 복제 노드를 저장하고 조회하는 용도로 활용된다.

깊은 복사를 위해서 복제 노드는 한번 씩만 사용되어야 한다. BFS 구현에서 큐는 각 요소가 중복되지 않음을 보장한다. 따라서, 최상위 노드를 꺼낼 때마다 해당 노드의 복제 노드를 처리한다.