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

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

예전에 JS로 풀었던 문제를 파이썬으로 다시 풀었다. 섬을 연결하고 있는 다리와 비용이 주어지고 최소 비용으로 모든 섬을 연결하는 문제이다. 파이썬으로 풀 때는 프림으로 풀었다.

JS

function solution(n, costs) {
    costs.sort((a, b) => a[2] - b[2]); //비용 순서대로 정렬
    let nodes = Array.from({length: n}, () => [])
    // console.log(costs)
    for (let i of costs) {
        nodes[i[0]].push(i[1])
        nodes[i[1]].push(i[0])
    }


    //크루스칼 알고리즘 사용
    let kgraph = Array.from({length: n}, () => []), tv = [], cyclechk=[false];

    for (let i = 0; i < costs.length; i++) {
        if(kgraph[costs[i][0]]){
            dfs(kgraph, costs[i][0], costs[i][1], cyclechk, [])//사이클 찾기
        }
        if (cyclechk[0]) { //사이클일 경우
            cyclechk[0] = false;
            continue;
        }
        let par = Math.min(costs[i][0], costs[i][1])
        let chi = Math.max(costs[i][0], costs[i][1])
        
        // 크루스칼로 그래프 만들기
        kgraph[par].push(chi)
        kgraph[chi].push(par)
        
        tv.push(costs[i])
    }

    // console.log();
    // console.log(tv);

    return tv.reduce((prev, curr) => {
        return prev + curr[2];
    }, 0)
}

function dfs(nodes, start, end, cyclechk, visited) {
    if(cyclechk[0]){
        return;
    }
      
    if (visited[start]) {
        return;
    }
    
    visited[start] = true;
    
    if (start == end){
        cyclechk[0] = true;
        return;
    }
    
    for (let i of nodes[start]) {
        if (!cyclechk[0]) {
            dfs(nodes, i, end, cyclechk, visited);
        }
    }
}

JS로 풀 때는 크루스칼 알고리즘을 사용했다. 간선으로 구성된 costs 배열을 ADJ 그래프로 바꿔줬고 크루스칼 그래프를 선언해줬다. costs 배열을 돌면서 dfs로 사이클을 확인하고 사이클이 아니면 숫자가 작은 노드를 parent로 삼아서 연결해줬다.

Python

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

def union(a, b, parent):
  pa = find(a, parent)
  pb = find(b, parent)
  
  parent[pa] = pb

def solution(n, costs):
  answer = 0
    
  costs.sort(key = lambda x: x[2])
  
  parent = [i for i in range(n+1)]
  
  for e in costs:
    a, b, cost = e
    if find(a, parent) != find(b, parent):
      answer += cost
      union(a,b, parent)
  
  return answer

costs를 비용 기준으로 오름차순 정렬하고 union-find를 활용해서 비용이 작은 간선부터 추가하고 사이클이 생성되지 않을 때에만 union이 발생하도록 했고 그때 비용을 계산해줬다.