[프로그래머스] 섬 연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 

제한사항

1. 섬의 개수 n은 1 이상 100 이하입니다.
2. costs의 길이는 ((n-1) * n) / 2이하입니다.
3. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
4. 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
5. 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
6. 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

 

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

풀이과정

처음에 DFS로 접근했다가 정답을 되지 않아 그리드로 접근하였다.

현재 방문한 노드를 저장하고 저장 된 노드 중 연결이 되는 곳 중 최솟값으로 건설이 가능한 구간을 찾아 연결시켜주었다.

 

예제풀이

1. 0번 노드에서 시작하여 1, 2 노드 중 가장 최솟값인 0->1(1)을 선택하였다.

2. 0, 1노드 중 최솟값인 1->3(1)를 선택하였다.

3. 0, 1, 2 노드 중 최솟값인 1->2(2)를 선택하였다.

4. 모든 노드가 연결되었으므로 종료한다.

 

 

소스코드(그리디)

function solution(n, costs) {
    var answer = 0;
    var map = new Array();
    for (var i = 0; i < n; i++) {
      var tmp = new Array(n);
      tmp.fill(0);
      map.push(tmp);
    }
    var visited = new Array(n);
    visited.fill(0);

    for (var i = 0; i < costs.length; i++) {
      var x = costs[i][0];
      var y = costs[i][1];
      var cost = costs[i][2];
      map[x][y] = map[y][x] = cost;
    }

    var node = new Array();
    node.push(0);
    visited[0] = 1;

    while(node.length < n) {
      var min = 987654321;
      var idx = -1;
      for (var i = 0; i < node.length; i++) {
        var curNode = node[i];
        for (var j = 0; j < n; j++) {
          if (map[curNode][j] != 0 && visited[j] == 0 && min > map[curNode][j]) {
            min = map[curNode][j];
            idx = j;
          }
        }
      }
      answer += min;
      visited[idx] = 1;
      node.push(idx);
    }
    return answer;
}

 

결과

 

 

Union Find

function solution(n, costs) {
  var answer = 0;
  var p = new Array(n);
  for (var i = 0; i < n; i++) p[i] = i;

  var edge = new Array();
  
  for (var i = 0; i < costs.length; i++) {
    edge.push({start : costs[i][0], end : costs[i][1], cost : costs[i][2]});
  }
  edge.sort(function(a, b) {return a.cost - b.cost;});

  function findParent(v) {
    if (v == p[v]) return v;
    return p[v] = findParent(p[v]);
  }
  function union(x, y) {
    x = findParent(x);
    y = findParent(y);
    p[x] = y;
  }
  for (var i = 0; i < edge.length; i++) {
    var x = findParent(edge[i].start);
    var y = findParent(edge[i].end);
    if (x != y) {
      union(x, y);
      answer += edge[i].cost;
    }
  }
  return answer;
}

결과