Clone Graph - 리트코드

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

평가

결과 : 성공
풀이시간 : 17분(실제로는 2시간이 넘었으나, 문제 유형에 따른 오류가 발생해서 시간을 낭비했습니다)

주의할 점

이 문제는 Solution의 static Map<Integer, Node> hash; 를 선언과 동시에 초기화해서는 안됩니다.
왜냐하면 이 문제는 계속해서 Solution을 실행하는 게 아니라, Solution의 cloneGraph 메서드를 반복적으로 실행합니다.
즉, cloneGraph()가 2번 발생하면, 2번째로 실행하는 메서드가 첫 번쨰로 실행한 메서드의 영향을 받을 수 있다는 의미입니다.

이거 때문에 로직은 틀린거 하나 없는데 계속 고민했습니다. 다른 분들의 풀이랑 전혀 다를게 없는 코드인데 어디서 틀렸는지 한참 찾았습니다.

아이디어

각 노드는 연결되어 있는 노드를 List로 관리합니다.
즉, 특정 노드를 복사할 때 연결되어 있는 노드들을 재귀로 복사해주면 쉽게 해결할 수 있는 문제입니다.

다만, 이미 방문한 노드에 대한 처리가 필요합니다. (그렇지 않으면 무한루프에 걸림)
노드는 방문한 순간 복사를 완료합니다.
따라서, 이미 방문한 노드의 경우 HashMap에 저장해 조회가 가능하게 만들어줍니다.

정답 코드

/*
// 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 {
    static Map<Integer, Node> hash;
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        hash = new HashMap<>();
        //node에는 인접 리스트가 neighbors로 있네
        return copyNode(node);
    }


    public static Node copyNode(Node old) {
        if (hash.containsKey(old.val)) {
            return hash.get(old.val);
        }
    
        Node copiedNode = new Node(old.val);
        hash.put(old.val, copiedNode);

        for(Node neighbor: old.neighbors) {
            copiedNode.neighbors.add(copyNode(neighbor));
        }
        return copiedNode;
    }   
}