(프로그래머스 JS)섬 연결하기

(프로그래머스 JS)섬 연결하기

728x90

반응형

SMALL

https://programmers.co.kr/learn/courses/30/lessons/42861?language=javascript

728x90

반응형

SMALL

union & find를 이용한 문제 풀이.

우선 parent를 저장하는 n 크기의 배열을 선언하여 자기 자신을 가리키도록 한다.

이후 costs를 비용의 오름차순으로 정렬.

for문으로 costs를 순회.

costs[0]은 출발점, costs[1]은 도착점이므로 unionFind 함수에 각 노드 번호를 전달해 parent를 찾는다.

만약 n번의 노드의 부모가 n이라면 그대로 n을 리턴해주고,

그렇지 않다면 루트의 번호를 계속 갱신해주도록 한다.

갱신이 끝나서 for문으로 다시 돌아와 if문을 검사한다.

start와 end => 시작점의 부모 번호와 도착점의 부모 번호가 같지 않다면 최소 비용으로 한번도 가지 않은 다리를 최소 비용으로 건넜다는 의미가 되기 때문에 answer += costs[i][2]를 더해준다.

또한, 이미 건넜다는 표시를 위해 parent[start] = end로 다시 갱신해주면 된다.

const unionFind = (n, parent) => { if(parent[n] === n){ return n; } return parent[n] = unionFind(parent[n], parent); } const solution = (n, costs) => { let answer = 0; const parent = Array(n).fill(0); for(let i = 0; i < n; i++){ parent[i] = i; } costs.sort((a, b) => a[2] - b[2]); for(let i = 0; i < costs.length; i++){ const start = unionFind(costs[i][0], parent); const end = unionFind(costs[i][1], parent); const cost = costs[i][2]; if(start !== end){ answer += cost; parent[start] = end; } } return answer; }

728x90

반응형

LIST

from http://eunchanee.tistory.com/608 by ccl(A) rewrite - 2021-11-10 10:26:22