-
leetcode top interview 150 | Clone Graph | BFSPS 2023. 9. 15. 09:24
Question
주어진 그래프를 클론한 그래프를 리턴.
그래프는 무방향으로 연결되어있고 노드마다 value와 주변 인접 노드들을 List에 넣어 가지고 있다.
인접노드들을 노드의 순서대로 담아 리턴해야한다.
Accepted Code
import java.util.*; class Solution { public Node cloneGraph(Node node) { if(node == null) return null; Queue<Node> queue = new LinkedList<>(); queue.add(node); Map<Node, Node> map = new HashMap<>(); map.put(node, new Node(node.val, new ArrayList<>())); while(!queue.isEmpty()){ Node visit = queue.poll(); for(Node neighbor : visit.neighbors){ if(!map.containsKey(neighbor)){ map.put(neighbor, new Node(neighbor.val, new ArrayList<>())); queue.add(neighbor); } map.get(visit).neighbors.add(map.get(neighbor)); } } return map.get(node); } }
Solve
노드를 순차적으로 탐색해야하기 때문에 방문한 노드의 인접 노드를 먼저 탐색하는 BFS로 접근해야겠다고 생각했다.BFS 탐색 :
그래프 탐색 방법 중 하나로 큐를 사용하여 같은 레벨에 있는 그래프들을 순차적으로 방문하고 그 다음 레벨을 탐색하는 방식
먼저 방문 노드를 담을 큐를 생성하고 input Node부터 순차적으로 탐색하기 위해 큐에 add해 놓는다.
그리고 노드를 방문할때 이미 방문한 노드를 재방문해서는 안되기 때문에, 방문여부를 체크하면서 해당 노드에 인접한 노드들을 탐색할때마다 저장하는 Map을 생성했다.
Map구조는 key의 중복이 불가능 하기 때문에 방문 노드를 key로 설정하고, value엔 새 노드를 만들어 방문 노드와 연결된 노드들의 정보를 계속해서 add하도록 하면
탐색이 끝나고 해당 map에서 input으로 들어온 node를 get해 리턴하면 될 것 같았다.
다음은 큐가 빌때까지 인접노드를 탐색하는 로직이다.
1. 큐에 있는 방문해야할 노드를 poll
2. 방문노드의 인접노드 리스트를 순차적으로 순회
3. 인접노드가 map에 저장되어있지 않으면 map에 key를 인접노드로 put하고 value엔 인접노드 정보들을 담을 노드를 초기화해준다. 그리고 다음 탐색을 위해 큐에 방문노드를 넣어준다. 1에서 방문한 노드의 인접노드 리스트에도 방문한 인접노드의 정보를 add하여 업데이트 해준다.
4. 인접노드가 map에 저장되어있으면 이미 방문한 노드기 때문에 1에서 poll해온 방문노드의 인접리스트에 인접노드 정보를 add하여 업데이트 해준다.
5. 그래프 모든 레벨 노드들의 탐색이 끝나면 input으로 들어온 node를 key로 갖는 value, 즉 인접노드가 연결되어있는 Node를 반환한다.
https://leetcode.com/problems/clone-graph/LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
'PS' 카테고리의 다른 글
java 프로그래머스 2018 카카오 블라인드 1차 셔틀버스 풀이 | Map, Queue 활용 (0) 2024.05.31 leetcode top interview 150 | Kth Largest Element in an Array | PriorityQueue (0) 2023.09.12 leetcode top interview 150 | Binary Tree Right Side View | DFS (0) 2023.09.06 leetcode top interview 150 | Find Peak Element | Binary Search (0) 2023.09.05 leetcode top interview 150 | Min Stack | ArrayList (0) 2023.09.01