133. Clone Graph

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

문제

그래프의 각 노드는 값(int)과 이웃 노드의 목록(List[Node])를 포함한다.

주어진 그래프를 deep copy 한 그래프를 반환하자

입력

• 무방향 그래프의 노드

출력

• 그래프의 deep copy 반환

---

나의 풀이

접근

deep copy만 하는 문제이기 때문에, 전체 탐색을 하며 각 노드를 deep copy 하면 된다고 생각했다.

1. 먼저 cur 노드 copy
2. 그 후에 주변 노드 temp list에 추가 후, 그 temp list를 cur노드의 neighbors에 추가

잘 되지 않았고, 다른 풀이를 보기로 했다.

---

다른 풀이

class Solution {
    public void dfs(Node node , Node copy , Node[] visited){
        visited[copy.val] = copy;
        for(Node n : node.neighbors) {
            if(visited[n.val] == null) {
                Node newNode = new Node(n.val);
                copy.neighbors.add(newNode);
                dfs(n , newNode , visited);
            } else {
                copy.neighbors.add(visited[n.val]);
            }
        }
    }
    public Node cloneGraph(Node node) {
        if(node == null) return null; 
        Node copy = new Node(node.val);
        Node[] visited = new Node[101]; 
        Arrays.fill(visited , null); 
        dfs(node , copy , visited);
        return copy;
    }
}

나는 계속, 새로운 노드를 전달하려 해서 기존의 neighbors 배열을 가져오는 데 문제가 있었지만, 이 코드는 기존 node와 새로 copy한 node 둘 다 전달했기 때문에, 해결할 수 있었다.