(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에서 관계를 맺고 있다.
해당 에러로 검색해보면 맞는것 같은데 왜 안되냐는 질문들이 꽤 있다. 문제 제출자가 원하는 방식으로 풀지 않아서 그런가보다 생각중이다. (아니면 내가 아직 파이썬에 대한 이해가 부족해서 그런걸수도 있을 것 같다.)
이후의 다른 케이스들에 대해서도 문제가 있을 수는 있겠지만, 적어도 위에 적은 케이스에 대해서 왜 통과를 못하는지는 확실히 모르겠다.
최종 코드
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 내용 추가)
해당 부분에 대해서 왜 풀리지 않는건지 도저히 이해가 안되었고 작성한 블로그 글을 커뮤니티 분들과 공유 해보았다.
몇몇 분들이 관심을 가져주셨고, 문제의 원인을 한 분이 찾아주셨다.
나는 사실 당연히 매 문제마다 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)이다.