박종훈 기술블로그

(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/

알게된 것

실패했던 이유 (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 이라고 이해하면 될 것 같다.

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

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Leetcode , graph , node , dfs , id , object reference