1. 섬 연결하기

섬들이 있는데 서로 다리를 통해서 연결되어있다. 연결시키는 다리에 비용이 들어간다. 그 비용도 다 알 수 있다. 이때 가장 적게 비용이 들어가는 다리만을 골라서 모든 섬이 통행되도록 연결한다고 했을때 , 들어가는 최소비용을 리턴하면 된다.

예를 들어, 아래와 같은 배열이 주어진다고 하자.

n              [island1,island2,cost]         return값
4	 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	   4

이때 n은 총 섬의 갯수이다. 그리고 배열안의 값을 살펴보자 [0,1,1] 라고 하면 0번과 1번 섬이 연결되어있고 비용은 1이 들었다는 뜻이다.

이걸 그림으로 나타내보자.

이때, 4개의 섬이 모두 연결되기 위해서 다리를 설치하는데 가장 비용이 적게 들어가는 다리를 설치한다고 하면 초록색 다리만을 선택하면 된다. 가장 효율적이고 탐욕스런 방법이다. 이때 들어가는 비용은 4이다.

2. 접근 방법

이건 그래프문제와 탐욕법 문제가 섞여있다. 다익스트라 최단거리 알고리즘과 비슷한 것 같다. 가장 적은 edge를 이용해서 각각의 노드가 연결되게 해야한다. 그리고 사이클이 이루어지면 안된다. 사이클을 말하기 전에 부모노드를 말해야 겠다. 부모노드는 각각의 섬이 최종적으로 도달하는 성지와 같은 곳이라고 보면 된다. 보통 부모노드는 가장 숫자가 적은 섬이다.

그럼 사이클로 다시 넘어와서, 여기서 말하는 사이클은 다음과 같다. 예를 들어, 0-1 / 0-2 면 1,2의 parent(0번 섬)는 같다. 이때 1-2를 연결하면 사이클이 형성된다고 한다.

사이클을 만들면 이미 통행이 가능한 섬에 또 다시 다리를 연결하는 셈이니 비효율이라고 판단되는 거다. 그래서 부모가 같을때는 연결하지 않는다. 이러한 방법으로 가장 cost가 적은 다리를 선택하여 섬을 하나씩 연결해갈때 우리는 모든 섬을 연결하면서 동시에 가장 적은 비용으로 연결할 수 있게 되는 것이다.

이러한 알고리즘을 크루스칼 알고리즘이라고 한다.

크루스칼 알고리즘은 최소한의 EDGE로 이루어진 TREE를 형성하는 알고리즘이다. 최소신장트리라고 한다. 그리고 union-find함수로 섬의 부모를 찾고(find) 부모가 같지 않으면 연결한다(union) 여기서 서로소 집합의 개념이 등장한다. 서로소 집합은 교집합이 없는 완전 다른 원소를 서로소 집합이라고 한다.

이 두 집합 사이에 겹치는 부분이 생기면 여기서 사이클의 개념으로 들어가는것이다. 서로의 parent가 같으면 연결하지 않고 아니면 union을 한다.

그래서 union은 서로의 부모를 일치시키는 작업이다(parent array안에서). 그리고 find(parent,x)함수는 x 의 부모를 찾아주는 함수이다. 그래서 a섬과 b섬의 부모를 find를 통해 찾고 같으면 pass아니면 union을 통해 부모를 일치시킨다.

그럼, parent가 같다는 것은 서로 통행할 수 있다는 뜻이다.

그럼 한 번 구현해보자!

// x의 parent를 찾아라!
// parent라는 것은 쭉 따라가다보면 결국 한곳으로 연결되는 지점을 뜻한다
// 연결되는 지점은 보통 가장 낮은 숫자의 island로 통일한다.
// 초반에는 자기 자신이 parent가 된다.
const find = (parent, x) => {
  let parentFound = parent[x];
  if (parentFound !== x) {
    // x는 island이름이다. x와 연결된 부모 island가 자신이 아니라면?
    // x부모의 부모를 또 거슬러 올라가서 찾아라
    parentFound = find(parent, parent[x]);
  }
  // x의 부모를 찾았으면 return
  return parentFound;
};

const union = (parent, a, b) => {
  a = find(parent, a);
  b = find(parent, b);
  // 작은 a,b 둘중에 parent를 비교해서 작은 parent를 parent에 등록
  a > b ? (parent[a] = b) : (parent[b] = a);
};

function kruskal(islandsNum, costs) {
  const parent = Array(islandsNum)
    .fill()
    .map((_, i) => i);

  // cost 중에 가장 적은것만 일단 선택하면서 island를 이어가는데
  // 이어가다가 parent가 같으면 연결(union)하지 않는다.
  // 왜냐면 parent가 같은데 굳이 또 연결할 필요는 없기 때문이다.

  // parent가 같은데도 연결되면 사이클이 이루어졌다고 표현한다
  // 예를 들어, 0-1 / 0-2 면 1,2의 parent는 같은데 이때 1-2를 연결하면 사이클이 형성됨

  // 가격을 이미 오름차순으로 sort했네?
  // 이렇게 하면 이미 가장 적은 비용으로 자동적으로 연결되게 될것이다
  costs.sort((a, b) => a[2] - b[2]);

  let sumCost = 0;

  costs.forEach((cost) => {
    // 사이클 생성 안됨 -> 연결 O
    if (find(parent, cost[0]) !== find(parent, cost[1])) {
      union(parent, cost[0], cost[1]);
      sumCost += cost[2];
    }
  });

  return sumCost;
}

이로써 크루스칼 알고리즘도 이해했다. 하나씩 차근차근 따라가다보니깐 어느순간 이해하게 되었다. 뿌듯하다 ㅎㅎㅎ 그럼 뿅!