programmers. 섬 연결하기

문제

문제

풀이

그래프에 굉장히 취약하다는 것을 깨닫게되었던 문제 중 하나

해당 정점까지의 거리를 더하지 않게끔 다익스트라 알고리즘을 응용해서 문제를 풀어 보려고 했지만 실패

풀이 방법은 다음과 같다

1. 간선들의 가중치 집합 costs를 가중치 기준으로 오름차순 정렬한다
2. 크기가 작은 가중치의 간선을 빼내서 잇는다
3. 이때 간선을 이어서 사이클이 형성되면 해당 간선은 버린다이때 앞의 두 간선말고 마지막의 간선을 버리는 이유 => 이미 costs를 오름차순으로 정렬했기 때문
4. 정점 A, B, C를 잇는 간선은 2개를 넘기면 최소비용을 얻을 수 없기 때문
5. 모든 섬이 연결될 때 까지 1~3 반복

여기서 3번 사이클이 형성되게 하는 간선을 찾는 것이 바로 Union-Find 알고리즘이다

각각의 섬을 index로 나타낸 배열에 연결된 섬의 정보를 벨류로 가지고 있게 한다

이어지지 않은 섬의 초기 배열상태는 다음과 같다

섬	0	1	2	3	4
최상위 섬	0	1	2	3	4

각각의 섬들은 자기 자신을 가르키고 있다

여기서 (0,1)의 간선을 이어주면

섬	0	1	2	3	4
최상위 섬	0	0	2	3	4

1번 섬은 0을 가리키고

(1,3) 간선을 이어주면

섬	0	1	2	3	4
최상위 섬	0	0	2	0	4

3번 섬은 1번 섬이 가르키는 0번 섬을 가르키게된다

이 때 (0,3)의 간선이 들어오면 어떻게 될까?

0->1->3->0 으로 사이클이 형성되기 때문에 간선을 이어줄 필요가 없다

(2,4)

섬	0	1	2	3	4
최상위 섬	0	0	2	0	2

(0,2)

섬	0	1	2	3	4
최상위 섬	0	0	0	0	0

모두 같은 값을 가지고 있으면 모든 섬이 이어진 것을 나타낸다

코드

    function isUnion(cycleTable) {
        const temp = cycleTable[0];
        return cycleTable.every(v=>v===temp);

    }

    function unionTable(from, to, cycleTable) {
        const temp = cycleTable[to];
        cycleTable[to] = cycleTable[from];

        for(let i=0; i< cycleTable.length;i++){
            if(cycleTable[i] === temp) cycleTable[i] = cycleTable[from];
        }
    }

    function solution(n, costs) {
        let answer = 0;
        costs.sort((a, b) => a[2]-b[2]);
        const cycleTable = Array(n).fill().map((_,i)=>i);

        while (!isUnion(cycleTable)) {
            const [from, to, cost] = costs.shift();
            if (cycleTable[from] === cycleTable[to]) continue;
            answer += cost;
            unionTable(from, to, cycleTable);
        }

        console.log(answer);

        return answer
    }