[Leetcode] 133. Clone Graph (python)

#1.  문제

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 

말 그대로 복사된 클론 그래프를 도출하는 문제

 

Input: 
adjList = [[2,4],[1,3],[2,4],[1,3]]

Output: 
[[2,4],[1,3],[2,4],[1,3]]

Explanation: 
There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

graph = {
    1: [2, 4],
    2: [1, 3],
    3: [2, 4],
    4: [1, 3],
}

---

#2.  풀이

 

문제 자체는 어렵지 않았는데 코드 구현에 어려움을 겪어서 결국 도움을 받았다.

그래프를 해시테이블 형태로 구현하고 생각해보면 크게 어렵지 않다.

graph = {
    1: [2, 4],
    2: [1, 3],
    3: [2, 4],
    4: [1, 3],
}

 

from typing import Optional
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def cloneGraph(self, node: Node) -> Node:

        if not node:
            return node

        graph = {}

        def dfs(node):

            # Base condition
            if node in graph:
                return graph[node]

            copied = Node(node.val)

            graph[node] = copied

            for neighbor in node.neighbors:
                copied.neighbors.append(dfs(neighbor))

            return copied

        return dfs(node)

문제 요구사항은 "복사본"을 도출해야 하는 것이므로 같은 값을 가진 copied 노드를 생성해야 한다.

깊이 탐색으로 node가 가진 인접한 노드들을 탐색하여 copied 노드에 넣어주면 같은 형태의 그래프가 나온다.