-
문제
https://programmers.co.kr/learn/courses/30/lessons/42861
코딩테스트 연습 - 섬 연결하기
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
programmers.co.kr
How to Solve ?
[1] 문제에 들어 가기 전에
이 문제를 풀기 위해서는 최소 스패닝(=신장) 트리를 해결 하기 위한 [ 크루스칼 / 프림 ] 알고리즘을 이해 하신 후에 풀 수 있는 문제라고 생각합니다.
1-1 ) 크루스칼
크루스칼은 '선'을 기준으로 최소 신장 트리를 찾는 알고리즘으로써, 선의 길이를 오름차순으로 정렬 한뒤 아래의 그림과 같이 순서대로 선을 연결 합니다.
다음과 같이 선을 연결하며, 찾을 때 발생 할 수 있는 문제는 "사이클이 생긴다" 라는 것인데, 사이클이 생기면 사이클 내부를 계속 돌며 값이 끊임없이 증가하거나 혹은 다른 모든 노드와 연결이 불 가능 해지기 때문에 이를 방지 할 수 있는 장치를 두어야 합니다.
이를 방지 할 수 있는 방법은 다양 하지만 일반적으로는 1) DFS 를 통해 노드를 탐색하는 방법을 채택하거나 2) union-find 라는 기법을 사용하여 연결 하고자 하는 노드의 부모가 같은지 확인하여 사이클의 유무를 확인 합니다.
1-2) 프림
프림 알고리즘은 "정점(=vertex)" 를 중심으로 최소 신장 트리를 찾는다는 점에서 크루스칼과 다릅니다.
프림은 임의의 간선은 선택하고, 선택한 간선의 정점으로부터 가장 낮은 가중치를 얻을 수 있는 정점을 n-1개의 간선이 연결 될 때까지 반복하여 문제를 해결 할 수 있습니다.
전체 코드
// default 상태에서의 부모는 자기 자신이다. // 만약 자기 자신이 아니라면, 다른 노드와 연결 된 것 임으로 // 그 값을 찾아서 반환 해주어야 한다. const find = (parent, x) => { if (parent[x] !== x) { parent[x] = find(parent, parent[x]); } return parent[x]; }; // 값이 더 작다는 것은, 선행된 노드이기에 // 선행된 노드에 간선을 연결 해주는 것이 옳다. const union = (parent, a, b) => { a = find(parent, a); b = find(parent, b); return a > b ? (parent[a] = b) : (parent[b] = a); }; function solve(n, costs) { // [0,1,2,3] // 정점을 0부터 시작했으면 [0,1,2] 로 구성해도 무관 const parent = Array.from({ length: n + 1 }, (v, i) => i); // 간선의 값을 오름차순으로 정렬 costs.sort((a, b) => a[2] - b[2]); let sum_cost = 0; costs.forEach((cost) => { // 부모가 다르다는건, 사이클이 없다는 것을 의미. if (find(parent, cost[0]) !== find(parent, cost[1])) { union(parent, cost[0], cost[1]); console.log(parent); sum_cost += cost[2]; } }); return sum_cost; } const [vertex, edge] = [3, 3]; const costs = [ [1, 2, 1], [2, 3, 2], [1, 3, 3], ]; console.log(solve(vertex, costs));
'PS > 프로그래머스' 카테고리의 다른 글
[ 프로그래머스_Lv2 ] 튜플 ( 문자열 - 자바스크립트 ) (0) 2021.06.26 [ 프로그래머스_Lv2 ] 파일명 정리하기 ( 문자열 - 자바스크립트 ) (0) 2021.06.23 [ 프로그래머스_Lv3 ] 단속카메라 ( 그리디 - 자바스크립트 ) (0) 2021.06.19 [ 프로그래머스_Lv2 ] 주식가격 ( 스택 - 자바스크립트 ) (0) 2021.06.18 [프로그래머스_Lv3] 네트워크 ( by using JavaScript ) (0) 2021.05.28 댓글