[프로그래머스] 섬 연결하기 - 자바스크립트

문제

프로그래머스

섬과 섬을 잇는 비용이 주어지고, 모든 섬끼리 통행이 가능한 최소의 비용을 구하는 문제다.

 

 

---

코드

function solution(n, costs) {
  let answer = 0;
  const length = costs.length;
  const parent = Array.from({ length }, (_, i) => i);

  costs.sort((a, b) => a[2] - b[2]);

  for (let i = 0; i < length; i++) {
    const [from, to, cost] = costs[i];
    if (findParent(parent, from) !== findParent(parent, to)) {
      unionParent(parent, from, to);
      answer += cost;
    }
  }

  return answer;
}

function findParent(parent, x) {
  if (parent[x] !== x) {
    parent[x] = findParent(parent, parent[x]);
  }
  return parent[x];
}

function unionParent(parent, x, y) {
  x = findParent(parent, x);
  y = findParent(parent, y);

  if (x < y) parent[y] = x;
  else parent[x] = y;
}

---

풀이

문제의 조건

1 <= n <= 100, n=섬의 갯수

costs 길이 <= ((n-1)*n)/2 <= 4950

costs[i]에는 [a, b, c]의 배열이 들어있으며, a섬에서 b섬까지의 비용 c를 의미

같은 연결은 주어지지 않으며 순서가 바뀌더라도 같은 연결로 본다. ( a섬에서 b섬으로의 비용c는 b섬에서 a섬으로의 비용c와 같다.)

모든 섬 사이의 다리 비용이 주어지지는 않으며, 연결할 수 없는 섬은 주어지지 않는다.

 

 

먼저 주어진 입출력을 바탕으로 시뮬레이션하면, 아래 그림의 순서를 거친다.

 

위와 같이 배열에서 parent 0에 모두 연결된다면, 모든 다리가 연결된 것이므로 더이상 다리를 건설할 필요가 없다.

 

"최소"의 비용을 구해야하므로, 우선 costs 배열을 비용 오름차순 정렬해야한다.

그리고 가장 저렴한 건설비용 순으로 다리건설여부를 판단한다.

 

건설여부 판단을 위해서는 a섬과 b섬의 연결여부를 알아야 한다.

a섬과 b섬이 직접적으로 연결되지 않았더라도, c섬이나 d섬을 경유하여 도착한다면 연결된 것이다.

그러므로 각 섬의 연결여부를 판단할 수 있는 배열이 필요하며, parent 배열로 삼았다.

 

parent 배열의 각 인덱스는 각 섬을 의미하며, 처음에는 자신을 원소로 가진다.

0번섬의 parent = 0번, 1번섬의 parent = 1번

 

섬이 연결될 때 마다, 더 크거나/작은 섬으로 parent 인덱스의 원소를 갱신해준다.

0번과 1번이 연결되었다면, 1번의 부모를 0으로 바꿔주거나, 0의 부모를 1로 바꾸면 된다.

0번과 1번 섬의 부모가 같다면, 이미 연결된 섬이므로 해당 다리는 건설할 필요가 없으니 넘어간다.

 

그렇게 모든 다리 건설 비용을 순회하면서, a섬 -> b섬의 연결을 확인하고, 다리건설을 하거나 하지 않으면 된다.

문제에서 연결할 수 없는 섬은 주어지지 않으므로, 다리 건설 비용을 모두 확인한 것 만으로도 모든 섬은 연결되게 된다.

 

알고리즘의 유형은 크루스칼이다.

크루스칼, 최소신장트리,  사이클이 존재하지 않는 그래프 등을 공부하면 되겠다.

---

주석을 포함한 코드

function solution(n, costs) {
  let answer = 0;
  const length = costs.length;
  const parent = Array.from({ length }, (_, i) => i);
  // 처음 parent 배열의 인덱스는 자신을 원소로 가진다.

  costs.sort((a, b) => a[2] - b[2]);
  // 최소비용을 구해야 하므로, 비용기준 오름차순 정렬한다.

  for (let i = 0; i < length; i++) {
    const [from, to, cost] = costs[i];
    if (findParent(parent, from) !== findParent(parent, to)) {
      // from, to 섬의 부모를 찾는다. 부모가 다르다는 것은, 서로 연결되지 않았다는 의미다.

	  unionParent(parent, from, to);
      answer += cost;
      // 부모가 연결되지 않았다면 다리를 건설한다. 부모를 연결해주고 다리 건설 비용을 더한다.
    }
  }

  return answer;
}

function findParent(parent, x) {
  if (parent[x] !== x) {
  	// x 인덱스의 부모가 x가 아니면, 다른 부모가 있는 것이다. 그 부모를 찾는다.
    // 결국 x 인덱스의 부모가 x 자신일 때, 재귀를 멈추게 된다.
    parent[x] = findParent(parent, parent[x]);
  }
  return parent[x];
}


function unionParent(parent, x, y) {
  // x, y 각각의 최종 부모를 찾는다.
  // 여기서는 낮은 인덱스를 부모로 삼을 예정이므로 x 부모가 더 작다면 y의 부모를 갱신하고
  // y 부모가 더 작다면 x의 부모를 갱신한다.
  x = findParent(parent, x);
  y = findParent(parent, y);
  
  if (x < y) parent[y] = x;
  else parent[x] = y;
}