[Java] 133. Clone Graph

문제 파악

노드로 연결된 그래프가 주어지고, 해당 그래프를 깊은 복사해서 반환해야한다.

 

---

풀이

1️⃣ bfs 를 이용한 풀이

💡 떠오른 Idea

깊은 복사를 하기 위해서는 어쩃든, 모든 노드에 방문해보고 해당 값을 갖는 새로운 노드를 생성해야한다.

문제에서 val 값은 unique 하다고 했으므로 map에 val 을 키값으로 해서 노드를 참조해준다.

첫번째 노드부터 이웃 노드들에 방문해보고, map에 들어있지 않은(아직 방문하지 않은) 노드들은 큐에 집어넣어 이웃 노드들에 방문하기를 반복한다.

만약 map에 들어있는(방문했던) 노드라면 큐에 넣지 않고 이웃으로서 추가만 해준다.

 

 

class Solution {
    Map<Integer, Node> map = new HashMap<>();
    Queue<Node> q = new LinkedList<>();

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

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

        q.offer(node);

        while (!q.isEmpty()) {
            Node poll = q.poll();

            for (Node n : poll.neighbors) {
                if (!map.containsKey(n.val)) {
                    Node newNode = new Node(n.val);
                    map.put(n.val, newNode);
                    q.offer(n);
                }

                map.get(poll.val).neighbors.add(map.get(n.val));
            }
        }

        return copied;

    }
}

 

 

결과

 

 

2️⃣ dfs를 이용한 풀이

💡 떠오른 Idea

bfs와 유사하다. dfs를 이용해서 모든 노드에 방문하고 이웃들을 복사해주면 된다.

 

class Solution {
    Map<Integer, Node> map = new HashMap<>();

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

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

        dfs(node);

        return copied;
    }

    private void dfs(Node node) {
        for (Node n : node.neighbors) {
            if (!map.containsKey(n.val)) {
                Node newNode = new Node(n.val);
                map.put(newNode.val, newNode);
                dfs(n);
            }

            map.get(node.val).neighbors.add(map.get(n.val));
        }
    }
}

 

결과

---

📖 회고

노드 클래스로 bfs 와 dfs를 구현하는게 처음에는 어색하고 힘들었는데,

 

결국에는 원리를 잘 파악해서 그대로 구현하면 원하는 결과를 얻을 수 있었다.

 

관련 문제를 많이 풀어봐야겠다는 생각이 들었다.