[리트코드] 133. Clone Graph #4
Description
133. Clone Graph
실패
카테고리
그래프, BFS
접근
- 방문처리 및 원본, 복제본 노드 저장을 위한 map 정의
- BFS용 큐 생성
- 큐가 빌때까지 해당 과정 반복
- 현재 노드를 꺼낸다
- 현재 노드의 이웃을 탐색하며 복제가 됐는지 확인한다 (map의 key값 확인)
- 복제가 되지 않은 경우에는 복제를 진행한다
- 현재 노드의 복제본에 이웃의 복제본을 연결한다
분석
O(N+E)
- BFS의 시간 복잡도
- N : 노드의 수, E : 엣지의 수
회고
복사에는 깊은 복사와 얕은 복사가 있다.
깊은 복사가 관건이었던 문제…