133. Clone Graph

엔지니어 게시판
[엔지니어 게시판 글쓰기 사용 방법]

[code]
게시글을 쓰실때 여기에 소스코드를 넣어주시면 코드가 깔끔하게 정리되어 보여집니다 :)
[/code]

133. Clone Graph

문제보기: https://leetcode.com/problems/clone-graph/

아이디어: DFS방법으로 Graph를 탐색한다. 그리고 Node를 Clone하기 위해 새로운 빈 Node를 하나 만든 후 neighbor에 인접 노드를 추가한다. 주어진 input은 각 node의 인접한 node를 나타낸다. 방문한 node는 HashMap을 이용하여 추적한다. 방문한 적이 있는 Node는 HashMap에서 가져와서 저장하고, 방문한 적이 없는 Node는 neighbor에 node를 추가해서 HashMap에 저장한다.


// Node definition

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}




class Solution {
    private HashMap<Node, Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        // case if it is null - the break condition of recursion.
        if(node == null){
            return node;
        }
        
        // tracking visited nodes
        if(visited.containsKey(node)){
            return visited.get(node);
        }
        
        // create a clone graph for the given nodes.
        Node result = new Node(node.val, new ArrayList());
        visited.put(node, result);
        
        // iterate neighbor nodes
        for(Node neighbor : node.neighbors){
            result.neighbors.add(cloneGraph(neighbor));
        }
        
        return result;
    }
}

, , ,

Comments

번호 분류 제목 글쓴이 날짜 조회
300 LeetCode솔루션 295. Find Median from Data Stream Rakulee 11.28 10
299 LeetCode솔루션 449. Serialize and Deserialize BST Rakulee 11.16 98
298 LeetCode솔루션 17. Letter Combinations of a Phone Number Rakulee 11.14 91
열람중 LeetCode솔루션 133. Clone Graph Rakulee 11.13 103
296 LeetCode솔루션 199. Binary Tree Right Side View Rakulee 11.10 110
295 LeetCode솔루션 326. Power of Three Rakulee 11.09 114
294 LeetCode솔루션 88. Merge Sorted Array Rakulee 11.08 141
293 LeetCode솔루션 328. Odd Even Linked List Rakulee 11.06 140
292 LeetCode솔루션 98. Validate Binary Search Tree Rakulee 11.05 168
291 코딩,소프트웨어 Dependency Injection (의존성 주입) Rakulee 11.03 202
290 IT,Tech 뉴스정보 Deep Link란? Rakulee 11.01 158
289 프로젝트 Hackathon Project Rakulee 10.28 223
288 코딩,소프트웨어 Enum 클래스를 활용한 상태 관리 Rakulee 10.25 180
287 IT,Tech 뉴스정보 KMM (Kotlin Multiplatform Mobile)을 이용한 공통 코드 개발 Rakulee 10.23 216
286 LeetCode솔루션 695. Max Area of Island Rakulee 10.21 343
285 IT,Tech 뉴스정보 Selenium을 활용한 브라우저 자동화 Rakulee 10.19 238
284 코딩,소프트웨어 Repository 패턴 Rakulee 10.19 229
283 코딩,소프트웨어 String 암호화 코드 Snippet Rakulee 10.17 217
282 IT,Tech 뉴스정보 Os.js, 자바스크립트 기반 운영체제 Rakulee 10.16 206
281 IT,Tech 뉴스정보 Postman을 이용한 RestAPI 테스트 Rakulee 10.13 215
280 코딩,소프트웨어 Android - Databinding 기능을 이용한 레이아웃 레벨에서의 값 변경 Rakulee 10.12 297
279 코딩,소프트웨어 Android 개발에서의 Navigation Graph 사용 Rakulee 10.11 332
278 코딩,소프트웨어 Android 개발에서 Countdownlatch를 활용한 디버깅 Rakulee 10.09 258
277 LeetCode솔루션 [10월 1주차] 995. Minimum Number of K Consecutive Bit Flips - Google, Ama… jack 10.04 374
276 LeetCode솔루션 [10월 1주차] 78. Subsets - Facebook, Amazon, ByteDance, Bloomberg, Google… 댓글+2 jack 10.04 655
275 LeetCode솔루션 [10월 1주차] 141. Linked List Cycle - Microsoft, Amazon, Bloomberg, Googl… 댓글+1 jack 10.04 347
274 코딩,소프트웨어 Android 개발에서의 Base 클래스 사용 Rakulee 10.03 282
273 LeetCode솔루션 136 Single Number 문제 풀이 영상 Rakulee 10.02 332
272 코딩,소프트웨어 Next.js 그거 어떻게 하는 건데. 룰루나비 09.30 308
271 LeetCode솔루션 [9월 5주차] 239. Sliding Window Maximum - Amazon, Facebook, Google, Goldm… 댓글+3 jack 09.27 602
270 LeetCode솔루션 [9월 5주차] 784. Letter Case Permutation - Amazon, Spotify, Apple, Micros… 댓글+2 jack 09.27 348
269 LeetCode솔루션 [9월 5주차] 338. Counting Bits - Google, Adobe 댓글+3 jack 09.27 349
268 LeetCode솔루션 [9월 4주차] 327. Count of Range Sum - Cisco jack 09.20 402
267 LeetCode솔루션 [9월 4주차] 128. Longest Consecutive Sequence - Google, Microsoft, Amazon… 댓글+4 jack 09.20 643
266 LeetCode솔루션 [9월 4주차] 303. Range Sum Query - Immutable - Facebook, Adobe 댓글+4 jack 09.20 599
265 LeetCode솔루션 235. Lowest Common Ancestor of a Binary Search Tree Rakulee 09.16 340
Category

State
  • 현재 접속자 69 명
  • 오늘 방문자 169 명
  • 어제 방문자 712 명
  • 최대 방문자 2,210 명
  • 전체 방문자 175,494 명
  • 전체 게시물 2,946 개
  • 전체 댓글수 380 개
  • 전체 회원수 492 명