[4주차] 133. Clone Graph

https://leetcode.com/problems/clone-graph/?envType=study-plan-v2&envId=top-interview-150 

LeetCode - The World's Leading Online Programming Learning Platform

---

📝 문제

무방향 그래프의 노드 하나가 주어진다. 해당 그래프를 깊은 복사를 수행 후, 새로운 그래프를 리턴하시오.

 

 

🎈 풀이

쉽게 풀 줄 알았는데 생각보다 시간이 걸렸다.

예제 그래프

처음 코드

private void dfs(Node src, Node dest) {
    for (Node nextNode : src.neighbors) {
        Node copiedNode = new Node(nextNode.val);
        dest.neighbors.add(copiedNode);

        if (visit.contains(nextNode.val)) continue;
        visit.put(copiedNode.val, copiedNode);
        dfs(nextNode, copiedNode);
    }
}

• visit: HashSet<Integer>

순회를 돌 때, 복사하는 대상은 노드의 방문 여부와 관계 없이 무조건 추가되어야 한다.

즉, 1을 방문 후, dfs로 노드 2 에서 자식을 복사 할 때, 노드 1 의 방문 여부와는 관계 없이 노드 2 의 이웃 복사본은 무조건 1, 3 이 들어가야 한다.

때문에 복사 로직을 6번 조건보다 위에 걸어서 해결하고자 하였다.

 

하지만 이렇게 되면 사실상 노드간의 연결이 끊어지게 된다. 무조건 new 를 통해 새로운 객체를 생성하였기 때문에 해당 코드를 실행하면 다음과 같은 그래프가 생성된다.

 

실행 결과 그래프

 

결국, 한번 생성한 복사본 노드는 반드시 주소를 가지고 있어야 한다.

때문에 visit 을 Set 에서 Map 으로 바꾸고, Key 에는 노드의 val, Value 에는 해당 노드 객체를 넣는 식으로 변경하였다.

그러면 현재 노드가 방문한 노드이면 Map 에서 해당 복사본을 꺼내고 이웃에 추가, 방문하지 않은 노드이면 new 로 새로운 노드를 생성 후, 이웃에 추가하고 Map에 넣으면 된다.

 

class Solution {
    private HashMap<Integer, Node> visit;

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        visit = new HashMap<>();
        Node res = new Node(node.val);
        visit.put(node.val, res);
        dfs(node, res);

        return res;
    }

    private void dfs(Node src, Node dest) {
        for (Node nextNode : src.neighbors) {
            if (visit.containsKey(nextNode.val)) {
                // 이미 생성된 노드 연결
                dest.neighbors.add(visit.get(nextNode.val));
            } else {
                Node copiedNode = new Node(nextNode.val);
                dest.neighbors.add(copiedNode);
                visit.put(copiedNode.val, copiedNode);
                dfs(nextNode, copiedNode);
            }
        }
    }
}