[Codility] Clone Graph

문제

 

분석

1. 딥카피를 해야 된다.

2. 리턴 값이 Node 인걸로 보아 인접 한 노드를 추가 해줘야 한다.

3. 주어진 대로 복사를 해야 되기 때문에 DFS 를 사용한다.

 

구현

import java.util.*;

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

        // 깊이 탐색을 위한 노드 스택 선언
        // 스택 -> DFS, 큐 -> BFS
        Stack<Node> nodeStack = new Stack<>();
        
        // 새로 생성한 노드를 저장하기 위한 맵
        Map<Integer, Node> map = new HashMap<>();

        // 처음 시작되는 노드를 넣어준다.
        nodeStack.push(node);

        // 처음 노드를 반환 값으로 쓴다.
        Node headerNode = copyNode(node);
        map.put(headerNode.val, headerNode);

        // 깊이 탐색 시작
        while(!nodeStack.empty()) {
        
            // 스택에 있는 노드를 꺼낸다.
            Node popNode = nodeStack.pop();

            // 새로 생성된 노드를 찾는다.
            Node findNode = map.get(popNode.val);
            for(Node neighbor : popNode.neighbors) {
               
               // 맵에 키가 없으면 아직 방문을 안했기 때문에 값을 넣어 준다.
               // 탐색을 위해 스택에 값을 넣어준다.
               if (!map.containsKey(neighbor.val)) {
                    map.put(neighbor.val, copyNode(neighbor));
                    nodeStack.add(neighbor);
                }
                // 노드에 인접한 노드를 추가 해준다.
                findNode.neighbors.add(map.get(neighbor.val));
            }
        }

        return headerNode;
    }

    public Node copyNode(Node node) {
        return new Node(node.val);
    }
}

 

 

결과