문제

• 완전히 같은 그래프여야 하나, 같은 노드여서는 안됨.
• Node 클래스가 따로 있음

풀이

• dfs (stack 이용)
• 어차피 최대 100개이므로 미리 visited 리스트와 출력 node들을 담은 nodeList를 생성함
• nodeList = [Node(i) for i in range(101)]로 미리 값을 초기화 해줌. (노드가 n개 일 때, 번호는 1~n+1로 생성된다고 조건에서 알려줌)
• 평범하게 dfs 탐색을 하나, node.val이 int 값이기 때문에 코드가 조금 난잡함
• node와 val은 미리 만들어 뒀으니, dfs 탐색을 하면서 neighbors만 잘 연결해주면 됨.
• 풀고 나니 단순한 dfs인데,,, Node class때문에 뇌정지 옴

    def cloneGraph(self, node: 'Node') -> 'Node':
        if node:
            nodeList = [Node(i) for i in range(101)] #미리 Node 생성
            visited = [False for _ in range(101)] # 방문 여부
            visited[0] = True  # place holder
            visited[node.val] = True
            stack = deque()
            stack.append(node)

            while stack:
                thisNode = stack.pop()
                for nextNode in thisNode.neighbors: #인접 노드 순회
                    nodeList[thisNode.val].neighbors.append(nodeList[nextNode.val]) # 새 그래프에 연결
                    if not visited[nextNode.val]:
                        visited[nextNode.val] = True
                        stack.append(nextNode) # 방문한적 없는 노드면, stack에 넣기

            return nodeList[node.val] # 첫번째 노드 반환
        else:
            return None

결과

굿!