섬 연결하기(★★★ / OO / 2) - Python / Javascript

개요

• 풀이 시간 : 30분
• 시간 제한 : -
• 메모리 제한 : -
• 기출 : 프로그래머스 Level 3 문제
• 링크 : https://programmers.co.kr/learn/courses/30/lessons/42861

문제

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

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

제한사항

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

입출력예

해결방법

너무나 쉬운 문제. 최소신장 문제이다. 이제는 안보고 풀려고 노력했고 10분만에 안보고 구현하는데 성공했다. 👏👏 최소신장문제는 간선을 비용순으로 내림차순으로 정렬하는게 첫번째. Union-Find를 이용해 사이클이 발생하는지 하지 않는지 조사하면서 사이클이 발생하지 않을때만 연결시켜주는게 두번째이다. 간단하지?

Python

내 코드

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def solution(n, costs):
    # 최소신장문제
    parent = [i for i in range(n)]  # 부모노드
    edges = []  # 간선

    for cost in costs:
        edges.append((cost[2], cost[0], cost[1]))

    # 1. 간선을 비용순으로 내림차순 정렬
    edges.sort(reverse=True)

    # 2. Union-Find로 사이클이 발생하는지 하지 않는지 조사
    # 사이클이 발생하지 않으면 연결
    result = 0
    while edges:
        cost, a, b = edges.pop()

        if find(parent, a) != find(parent, b):
            union(parent, a, b)
            result += cost

    return result

Javascript

내 코드

const find = (parent, x) => {
  if (parent[x] !== x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
};

const union = (parent, a, b) => {
  a = find(parent, a);
  b = find(parent, b);

  return a > b ? (parent[a] = b) : (parent[b] = a);
};

function solution(n, costs) {
  const parent = Array(n)
    .fill()
    .map((_, i) => i);
  costs.sort((a, b) => a[2] - b[2]);
  // console.log(parent, costs);

  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;
}

console.log(
  solution(4, [
    [0, 1, 1],
    [0, 2, 2],
    [1, 2, 5],
    [1, 3, 1],
    [2, 3, 8],
  ]),
);

구현 방식은 동일하다. 다만 파이썬과 자바스크립트 내장 함수 사용법이 다 다르기 때문에 약간의 차이만 있을 뿐이다.

참고로 처음에 구현할 때 아래처럼 for...of 문을 사용해서 구현해줬는데 내 실행환경에서는 잘 동작하는 반면 프로그래머스 실행환경에서는 에러가 발생하였다.

for ([a, b, s] of costs) {
  // 사이클 생성 안됨 -> 연결 O
  if (find(parent, a) !== find(parent, b)) {
    union(parent, a, b);
    console.log(parent);
    sumCost += s;
  }
}

되도록이면 for...of문 사용은 자제해야 할듯...🤷‍♂️;;