👓 문제 요약
섬을 연결해!! 최소비용으로!
뭐? 어디서 본 거 같은데 ??
최소신장트리(MST) !!
자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
최소신장트리를 푸는 유명한 2가지 방법이 있다.
- 크루스칼 알고리즘
- 프림 알고리즘
솔직히 둘이 좀 헷갈린다. 최소비용 부터 시작하는게 크루스칼 이였나??? 프림인가??
우리는 크루스칼 알고리즘 (포스트 적으면서 외움)으로 한번 해보자!
더 쉽거든
간략하게 크루스칼 알고리즘이 뭐냐면..
- 가장 적은 비용의 간선을 선택해서 이어나감.
- 🛑간선을 추가하게 되면 사이클이 형성될 경우 간선을 추가하지 않음🛑
사실 두번째 내용이 핵심이다.
제일 적인 비용의 간선은 정렬하고 추가해 나가면 되는데, 사이클의 유무를 따지는게 여간 귀찮은게 아니다.
나에게 가장 쉬운 방법은 간선을 추가할 때마다 노드들(여기선 섬)끼리 그룹화 하는 것이다.
다들 자신에게 편한 방법으로 하세용~
그룹화해서 노드를 연결 했을 때 같은 그룹에 속해있나 아닌가만 따지면 된다.
예를 들어 다음과 같이 상황이 놓여져 있다고 생각하자
1 - 2 - 3 이 하나의 그룹이고 대표는 1이다.
4 - 5 - 6 이 하나의 그룹이고 대표는 4이다.
만약 노드4 와 노드6 의 간선이 있다고 생각하고 연결해보려고 하자.
노드4 의 대표는 노드4 이고, 노드6 의 대표도 노드4 이다. 같은 그룹이라는 것이다.
만약 노드 5와 노드 6 을 연결하려고 하면 서로의 대표가 다르기 때문에 가능하다는 것이다!!!!!!!!!!!
이 경우 노드 4,5,6 의 대표를 바꾸어 주어야한다. 이렇게 숫자로 주어진 경우는 단순하게 대표 4의 값을 6으로 바꾸어주면 된다.
그럼 노드 6을 선택하면 그룹 대표인 노드 4, 다시 4의 대표는 노드 1 ... 알겠지용,,?
6-> 4-> 1
노드가 숫자로 주어지면 이렇게 푸는게 나은거 같습니다!!
🥽 소스코드 및 소스해석
let group = new Array(128);
function solution(n, costs) {
var answer = 0;
costs.sort((a, b) => {
return a[2] - b[2];
});
for (let index = 0; index < n; index++) {
group[index] = index;
}
for (let index = 0; index < costs.length; index++) {
let groupA = travel(costs[index][0]);
let groupB = travel(costs[index][1]);
if (groupA === groupB) continue;
answer += costs[index][2];
group[groupA] = groupA < groupB ? groupA : groupB;
group[groupB] = group[groupA];
}
return answer;
}
const travel = (n) => {
if (n === group[n]) return n;
else return travel(group[n]);
};
solution(6, [
[0, 1, 5],
[0, 3, 2],
[0, 4, 3],
[1, 4, 1],
[3, 4, 10],
[1, 2, 2],
[2, 5, 3],
[4, 5, 4],
]);🔨 문제 후기
오늘 코딩테스트 보고 나는 왜이리 멍청하지 하다가 이 문제를 풀고 희망을 가졌다.
나도 풀 수 있따!.
물론 저보다 더 잘하는 사람이 많을 것 입니다... 겸손하자...
