[Leetcode Top Interview 150] 133. Clone Graph

난이도 : medium

문제링크

• 연결 무방향 그래프의 노드가 주어진다
• deep copy된 그래프의 노드를 리턴하라
• 각 노드의 값은 유일하다

 

1. 접근법

• 노드를 BFS 탐색하여 새로운 노드를 탐색할 때마다 clone함

 

2. 의사코드

// Queue에 node 노드 추가
queue.offer(node)

// queue가 비어있지 않을때까지 반복
while (!queue.isEmpty()) {
	// 가장 최근에 들어온 것 뽑음
	Node cur = queue.poll(); 
    
	// cur의 이웃 순회
    for (Node neighbor : cur.neighbors) {
     	// 방문하지 않았던 이웃이라면
        if (!map.containsKey(neighbor)) {
	        // 큐에 추가
        }
        
        // 현재 노드에 이웃 추가
    }
}

 

3. 구현 코드

public Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }

    Map<Node, Node> map = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();

    Node clone = new Node(node.val);
    map.put(node, clone);

    queue.offer(node);

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

        for (Node neighbor : cur.neighbors) {
            if (!map.containsKey(neighbor)) {
                map.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            map.get(cur).neighbors.add(map.get(neighbor));
        }
    }

    return clone;
}

• 복제한 노드를 가져오기 위해서, map 자료구조를 사용함
  • Map<원본노드, 복제노드>

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함