<Medium> Clone Graph (LeetCode : C#)

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

📕 문제 설명

연결된 무방향 그래프의 node 참조가 주어질 때 해당 그래프를 deep copy해서 반환하기

class Node {
    public int val;
    public List<Node> neighbors;
}

입력의 경우 adjList 형태로 주어지는데 neighbor를 나타내는 리스트이다.

adjList[i] = i번째 노드의 neighbor index 목록

• Input
  노드 정보
• Output
  deep copy한 결과

예제

풀이

주어진 처음 노드에서 인접 리스트를 순회하면서 어떻게 clone할지만 생각해보면 되는 문제다. queue를 사용해서 neighbor들 방문을 각각 진행할 수 있게 작성하였고 딕셔너리를 하나 두어 node 정보를 새롭게 만들 수 있게 하였다.

/*
// Definition for a Node.
public class Node {
    public int val;
    public IList<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new List<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new List<Node>();
    }

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

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

        Dictionary<int, Node> visited = new Dictionary<int, Node>();
        visited[node.val] = new Node(node.val);
        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(node);

        while (queue.Count > 0)
        {
            Node currNode = queue.Dequeue();

            foreach(Node neighbor in currNode.neighbors)
            {
                if (visited.TryGetValue(neighbor.val, out Node neighborNode))
                {
                    visited[currNode.val].neighbors.Add(neighborNode);
                }
                else
                {
                    visited[neighbor.val] = new Node(neighbor.val);
                    visited[currNode.val].neighbors.Add(visited[neighbor.val]);
                    queue.Enqueue(neighbor);
                }        
            }
        }

        return visited[node.val];
    }
}

결과

시간 의미 x