[LeetCode] 133. Clone Graph

😎풀이

해당 문제는 모든 노드를 복사된 노드로 replace 해야하는 문제이다.

dfs를 통해 재귀적으로 함수를 호출하며 이웃 노드들을 clone하는 방식으로 풀이하였음

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     neighbors: _Node[]
 * 
 *     constructor(val?: number, neighbors?: _Node[]) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.neighbors = (neighbors===undefined ? [] : neighbors)
 *     }
 * }
 * 
 */


function cloneGraph(node: Node | null): Node | null {
    // 방문한 노드를 저장하는 Map
    // key: 원본 노드, value: 복제된 노드
    const visited = new Map<Node, Node>();
    
    // DFS를 수행하는 함수
    function dfs(originalNode: Node | null): Node | null {
        // 기본 케이스: 노드가 null이면 null 반환
        if (!originalNode) return null;
        
        // 이미 방문한 노드라면 복제된 노드 반환
        if (visited.has(originalNode)) {
            return visited.get(originalNode)!;
        }
        
        // 새로운 노드 생성 (이웃 노드들은 아직 빈 배열)
        const cloneNode = new Node(originalNode.val, []);
        
        // 방문 맵에 추가
        visited.set(originalNode, cloneNode);
        
        // 이웃 노드들을 순회하면서 재귀적으로 복제
        for (const neighbor of originalNode.neighbors) {
            cloneNode.neighbors.push(dfs(neighbor)!);
        }
        
        return cloneNode;
    }
    
    return dfs(node);
}