|
| 1 | +const fs = require('fs'); |
| 2 | +const stdin = (process.platform === 'linux' |
| 3 | + ? fs.readFileSync('/dev/stdin').toString().trim() |
| 4 | + : `6 |
| 5 | +9 |
| 6 | +1 2 5 |
| 7 | +1 3 4 |
| 8 | +2 3 2 |
| 9 | +2 4 7 |
| 10 | +3 4 6 |
| 11 | +3 5 11 |
| 12 | +4 5 3 |
| 13 | +4 6 8 |
| 14 | +5 6 8 |
| 15 | +` |
| 16 | +).split('\n'); |
| 17 | + |
| 18 | +const input = (() => { |
| 19 | + let line = 0; |
| 20 | + return () => stdin[line++]; |
| 21 | +})(); |
| 22 | + |
| 23 | +const N = parseInt(input()); |
| 24 | +const M = parseInt(input()); |
| 25 | + |
| 26 | +const parent = {}; |
| 27 | +const rank = {}; |
| 28 | + |
| 29 | +// 아래 세개의 함수는 승영님 코드 참고(최적화된 유니온 파인드) |
| 30 | +function init(v) { |
| 31 | + parent[v] = v; |
| 32 | + rank[v] = 0; |
| 33 | +} |
| 34 | + |
| 35 | +function findParent(v) { |
| 36 | + if (parent[v] !== v) { |
| 37 | + parent[v] = findParent(parent[v]); |
| 38 | + } |
| 39 | + return parent[v]; |
| 40 | +} |
| 41 | + |
| 42 | +function unionParent(v, u) { |
| 43 | + const root1 = findParent(v); |
| 44 | + const root2 = findParent(u); |
| 45 | + if (root1 !== root2) { |
| 46 | + if (rank[root1] > rank[root2]) { |
| 47 | + parent[root2] = root1; |
| 48 | + } else { |
| 49 | + parent[root1] = root2; |
| 50 | + if (rank[root1] == rank[root2]) { |
| 51 | + rank[root2]++; |
| 52 | + } |
| 53 | + } |
| 54 | + } |
| 55 | +} |
| 56 | + |
| 57 | +const computers = []; |
| 58 | + |
| 59 | +for (let i = 0; i < M; i++) { |
| 60 | + computers.push( |
| 61 | + input() |
| 62 | + .split(' ') |
| 63 | + .map((A) => parseInt(A)) |
| 64 | + ); |
| 65 | +} |
| 66 | + |
| 67 | +for (let i = 0; i < N; i++) { |
| 68 | + init(i); |
| 69 | +} |
| 70 | + |
| 71 | +// 비용을 오름차순으로 정렬 |
| 72 | +computers.sort((a, b) => a[2] - b[2]); |
| 73 | + |
| 74 | +let cost = 0; |
| 75 | + |
| 76 | +for (let i = 0; i < M; i++) { |
| 77 | + const left = computers[i][0]; |
| 78 | + const right = computers[i][1]; |
| 79 | + const eachCost = computers[i][2]; |
| 80 | + |
| 81 | + if (findParent(left) !== findParent(right)) { |
| 82 | + cost += eachCost; |
| 83 | + unionParent(left, right); |
| 84 | + } |
| 85 | +} |
| 86 | + |
| 87 | +console.log(cost); |
| 88 | + |
| 89 | +/* |
| 90 | +
|
| 91 | +## How |
| 92 | +유니온파인드 문제였다. 예전에 프로그래머스 섬 연결하기 문제를 못풀었던 기억이 있어서 유니온 파인드에 대해서 이해하자는 마음가짐으로 접근했다. 처음에는 문제 어떻게 풀어야할지 모르겠어서 포기했다가 유니온파인드 문제라는 것을 알고 동빈님 강의와 승영님이 정리해두신걸 보고 왜 이것을 적용해야하는지 이해할 수 있었다. |
| 93 | +
|
| 94 | +결론적으로 최소비용이 들게끔 전체 네트워크가 연결된 상황(MST)를 구해야하는 문제이다. 유니온 파인드를 이용해 그래프를 표현할 때 원소가 최상의 부모 노드를 가리킨다는 특성을 이용하면 된다. 컴퓨터 비용이 낮은 순으로 정렬해서 두 컴퓨터의 부모가 다르다면 그만큼 비용을 증가시키고 unionParent 함수로 합쳐주는 과정을 반복하면 해결할 수 있다. |
| 95 | +
|
| 96 | +## Retrospective |
| 97 | +여러 코드들과 강의 및 글들을 참고하긴 했지만 유니온 파인드가 무엇인지 이해할 수 있는 유익한 시간이었다. 섬 연결하기 문제를 혼자힘으로 풀어보아야겠다. |
| 98 | +
|
| 99 | +*/ |
0 commit comments