박종훈 알고리즘 블로그

(Leetcode) 133 - Clone Graph

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


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

133번 문제는 그래프와 관련된 문제이다.

처음에는 아래와 같이 코드를 작성하였는데 통과하지 못했다. 그리고 왜 통과하지 못했는지 이해를 아직도 못하고 있다. 물론 다른 방식으로 코드를 제출하여 통과는 하였다. (최하단에 정리)

from typing import Optional

class Solution:
    nodeList = {}
    done = {}

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not hasattr(node, 'val'):
            return None

        root = Node(val=node.val)

        self.nodeList[node.val] = root

        if len(node.neighbors) > 0:
            self.search(node.val, node.neighbors)

        return root

    def search(self, val, neighbors):
        if val in self.done:
            return

        self.done[val] = True

        for item in neighbors:
            if item is not None:
                if hasattr(item, 'val'):
                    if item.val not in self.nodeList:
                        self.nodeList[item.val] = Node(val=item.val)

                    if not any(node.val == item.val for node in self.nodeList[val].neighbors):
                        self.nodeList[val].neighbors.append(self.nodeList[item.val])

                    if item.neighbors is not None:
                        self.search(item.val, item.neighbors)

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

다른 사람들의 코드와 비교해봤을 때 좋은 코드가 아니라는 것에는 동의하나 왜 테스트에 통과하지 못하는지는 이해가 되지 않았다.

디버깅 시도 기록

[[2],[1]]

위 케이스에 대해서 You must return a copy of all the nodes in the original graph 이라는 에러메시지를 출력하며 테스트가 계속 실패하였다.

그래서 아래와 같이 출력을 해가며 디버깅을 해보았다.

solution = Solution()

node1 = Node(val=1)
node2 = Node(val=2)
node1.neighbors.append(node2)
node2.neighbors.append(node1)

result3 = solution.cloneGraph(node1)

print(result3.__dict__)
print(result3.neighbors[0].__dict__)
print(result3.neighbors[0].neighbors[0].__dict__)
print(result3 is result3.neighbors[0].neighbors[0])
print(result3.neighbors[0]
        is result3.neighbors[0].neighbors[0].neighbors[0])

print(id(result3),
        id(result3.neighbors[0]),
        id(result3.neighbors[0].neighbors[0]),
        id(result3.neighbors[0].neighbors[0].neighbors[0]))

그리고 출력 결과는 다음과 같았다.

{'val': 1, 'neighbors': [<__main__.Node object at 0x10461ff10>]}
{'val': 2, 'neighbors': [<__main__.Node object at 0x10461ffd0>]}
{'val': 1, 'neighbors': [<__main__.Node object at 0x10461ff10>]}
True
True
4368498640 4368498448 4368498640 4368498448

출력을 해보면 정상적으로 노드1 과 노드2 가 있고 서로가 서로를 neighbors에서 관계를 맺고 있다.

graph

해당 에러로 검색해보면 맞는것 같은데 왜 안되냐는 질문들이 꽤 있다. 문제 제출자가 원하는 방식으로 풀지 않아서 그런가보다 생각중이다. (아니면 내가 아직 파이썬에 대한 이해가 부족해서 그런걸수도 있을 것 같다.)

이후의 다른 케이스들에 대해서도 문제가 있을 수는 있겠지만, 적어도 위에 적은 케이스에 대해서 왜 통과를 못하는지는 확실히 모르겠다.

최종 코드

dfs로 해결하였다.

from typing import Optional

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not hasattr(node, 'val'):
            return None

        nodeList = {}

        def dfs(node):
            if node in nodeList:
                return nodeList[node]

            clone = Node(val=node.val)

            nodeList[node] = clone

            for neighbor_node in node.neighbors:
                clone.neighbors.append(dfs(neighbor_node))
            return clone

        return dfs(node)


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

참고한 블로그 : https://www.algodale.com/problems/clone-graph/

알게된 것

  • 파이썬은 함수 안에 함수를 정의할 수 있다.
  • hasattr 를 통해서 특정 속성(attribute)가 있는지 확인해볼 수 있다.
  • __dict__ 를 통해서 객체 내부를 프린트 해볼 수 있다. (일부이긴 하지만)
  • dictionary 구조의 key값으로 객체 를 넣어도 된다.

실패했던 이유 (24.02.18 내용 추가)

해당 부분에 대해서 왜 풀리지 않는건지 도저히 이해가 안되었고 작성한 블로그 글을 커뮤니티 분들과 공유 해보았다.

몇몇 분들이 관심을 가져주셨고, 문제의 원인을 한 분이 찾아주셨다.

contribute

나는 사실 당연히 매 문제마다 Solution 객체를 재생성 할 줄 알았는데 적어도 이 문제에 한해서는 Solution 객체를 재사용하고 있다는 것을 알게되었다.

그래서 로컬 변수로 바꿔주거나 아래와 같이 cloneGraph 시작 부분에 변수를 초기화 해줘야 했다.

def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
    self.nodeList = {}
    self.done = {}
    # ...

그리고 찾아보면서 class variable 과 object variable에 대해서 알게 되었다. class variable는 java로 치면 static 이라고 이해하면 될 것 같다.

이전에는 몰라서 썼던거인지라 이 이후로는 클래스 변수를 쓰는건 자제하고 있다. 파이썬에 조금씩 익숙해져 가는 것 같다.

Java 로 다시 풀기

class Solution {
    public Node cloneGraph(Node node) {
        return cloneGraph(new HashMap<>(), node);
    }

    private Node cloneGraph(Map<Integer, Node> map, Node node) {
        if(node == null) {
            return null;
        }

        if (map.containsKey(node.val)) {
            return map.get(node.val);
        }

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

        for (int i = 0; i < node.neighbors.size(); i++) {
            Node neighborNode = node.neighbors.get(i);
            copy.neighbors.add(map.getOrDefault(neighborNode.val, cloneGraph(map, node.neighbors.get(i))));
        }

        return copy;
    }
}

그래프 용어 정리

  • vertex : 정점 (= node)
  • edge : 간선

TC, SC

node(vertex)의 수를 V, edge의 수를 E 라고 하였을 때 각 노드 마다 edge의 수만큼 반복을 해야한다. 시간 복잡도는 O(V + E) 이다. 공간 복잡도는 O(V)이다.