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

woolee의 기록보관소·2023년 1월 24일

Algorithms 알고리즘개념정리

알고리즘 문제풀이

목록 보기

150/178

문제 출처

프로그래머스 lev3 - 섬 연결하기

나의 풀이 (실패)

풀이 시도는 대략 이렇다.

우선, n개의 섬을 연결하기 위해서 필요한 간선으로 경우의 수를 나눴다.
n-1개의 간선으로 연결한 경우부터 시작해서 (n-1)*n / 2 개의 간선으로 연결한 경우들을 모아서 Math.min(a, b, ...) 하면 되지 않을까라는 생각을 먼저 했다.

그래서 섬(isle)을 0으로 채워넣고 일단 costs를 단일 반복을 진행하면 연결 상황을 정리해놨다.

그리고 나서 costs 배열의 index를 기준으로 각 index들을 선택하는 조합 경우의 수(1개를 선택하거나, 2개를 선택하거나 ...) 즉, 부분집합을 미리 배열(cases)로 구해놓았다.

그리고 cases 배열을 순회하면서 각 경우의 수에 맞게 연결을 끊고 나서,
그렇게 끊었는데도 각 섬의 값이 0이 아니면서 동시에 각 섬들의 합이 (1*2 + (n-2)*2) 보다 큰 경우에만 값을 찾아놓는다.

그리고 이 값들 중 최소값이 정답이 되도록 했으나 망했다.

function solution(n, costs) {
  let isle = new Array(n).fill(0)
  let answer = 0

  costs.map(_ => {
    const [a, b, cost] = _
    isle[a]++
    isle[b]++
    answer += cost 
  })

  // 0 ~ (n-1)*n/2 까지의 부분집합
  let pick = new Array(costs.length).fill().map((_,i) => i)
  // fill()만 하면 배열이 undefined로 채워지고, 이 값들을 가지고 map 메서드를 사용하면 index를 값으로 채워넣은 새로운 배열을 반환하게 된다. 
  let cases = [];

  // n개의 부분집합은 2^n이므로 비트마스크를 사용해 부분집합을 구했다. 
  for(let i = 1; i < (1 << pick.length); i++) {
    cases.push([]);
    for(let j = 0; j < pick.length; j++) {
        if(i & (1 << j)) cases[i-1].push(pick[j])
    }
  }

  let res = []
  // console.log(cases)
  cases.map(v => {
    let copyArr = [...isle]
    let copySum = answer 

    v.map(x => {
      const [a, b, cost] = costs[x]
      copyArr[a]-- 
      copyArr[b]-- 
      copySum -= cost
    })
    // console.log(copyArr, copySum)
    let flag = false 

    for(let i=0; i<copyArr.length; i++){
      if(copyArr[i] === 0){
        flag = true 
        break 
      }
    }

    if(!flag){
      let edge = copyArr.reduce((a,b) => a+b, 0)
      if(edge >= (1*2 + (n-2)*2) ){
        // console.log(isle, v, copyArr, copySum)
        res.push(copySum)
      }
    }
  }) 
  // console.log(res)
  return Math.min(...res)
}

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

Union-Find

Union-Find (합집합 찾기)

UF는 대표적인 그래프 알고리즘이다. 서로소 집합(Disjoint-Set, 서로 같은 집합이 아닌) 알고리즘이라고도 부른다.

여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

모든 노드가 연결되지 않은 상태일 때부터 시작한다. 이때의 각 노드의 부모는 자기 자신이 된다.

이때 노드끼리 연결되었다면, 이걸 프로그래밍 언어로 어떻게 표현해야 할까?

=> 예를 들어 1과 2가 연결되었다면, 1과 2 중에서 더 작은 값인 1을 부모로 가지도록 부모 값을 업데이트 해주면 된다.
=> 이렇게 부모를 합칠 때는 더 작은 값으로 합치며, 이것 Union이라고 한다.
=> 1과 2가 연결된 상태에서, 2와 3을 연결하면 3의 부모는 2가 된이때 1과 3은 2를 통해 연결되어 있지만, 3의 부모는 2로 되어 있다. 이걸 해결하기 위해 재귀 함수가 사용한다.

이렇듯 Union-Find는 두 개의 노드의 부모 노드를 확인해 현재 같은 집합에 속하는지 확인하는 알고리즘이다.

#include <stdio.h>

// 부모 노드를 찾는 함수 
int getParent(int parent[], int x){
  if(parent[x] == x) return x;
  return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수 (== 그래프로 연결하는 함수)
int unionParent(int parent[], int a, int b){
  a = getParent(parent, a);
  b = getParent(parent, b);
  if(a < b) parent[b] = a; // b가 더 큰 값이면 b의 부모가 a가 될 수 있도록 
  else parent[a] = b 
}

// 같은 부모를 가지는지 확인하는 함수 (== 같은 그래프에 속하는지 확인)
int findParent(int parent[], int a, int b){
  a = getParent(parent, a);
  b = getParent(parent, b);
  if(a == b) return 1; // 같은 부모면 1 아니라면 0 (같은 그래프라면 1 아니라면 0) 
  return 0; 
}

int main(void){
  int parent[11];
  for(int i = 1; i <= 10; i++){
    parent[i] = i;  // 처음 시작은 자기 자신을 부모로 가리키도록 
  }
  // 여기서부터 그래프 연결을 한 뒤,
  unionParent(parent, 1, 2)
  ... 
  
  // 같은 그래프인지 판별 하는 과정  
  findParent(parent, 1, 5)
  ... 
}

Kruskal

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리(MST, Minimum Spanning Tree)를 만들기 위한 대표적인 알고리즘이다.

노드 == 정점 == 도시, 건물 등
간선 == 거리 == 비용

특징은 가장 적은 비용으로 모든 노드를 연결하고자 할 때 사용되는 간선의 개수는 반드시 노드 개수 - 1개이다.

크루스칼 알고리즘의 핵심 개념은 간선을 거리가 짧은 순서대로 그래프에 포함시킨다는 것. (=> 정렬을 한 뒤에 짧은 순서대로 그래프에 포함시키므로, 그루스칼은 그리디 알고리즘에 속한다.)

모든 노드를 최대한 적은 비용으로 '연결'만 시키면 되므로 모든 간선 정보를 오름차순 정렬한 뒤, 비용이 적은 간선부터 하나씩 그래프에 포함시키면 끝난다.

주의할 점으로는, 최소 비용 신장 트리에서는 사이클이 발생하면 안 된다. 즉, 1~3 노드 3개가 있을 때 1과 2를 연결하고 2를 3과 연결하면 되는데, 여기서 1과 3까지 연결하면 사이클이 발생한다.
=> 사이클이 발생하는 지 여부를 체크하기 위해 Union-Find 알고리즘을 사용한다.

정리하자면

모든 간선들을 거리(비용)을 기준으로 오름차순 정렬을 한다. 정렬된 순서에 맞게 그래프에 포함시키되,
포함시키기 전에 사이클 테이블을 확인해서
사이클을 형성하지 않는 경우에만 간선을 포함한다.

다른 풀이

크루스칼 알고리즘

항상 그리디 유형은 정렬을 한 뒤에 작은 값부터 포함시키는 로직을 고려하는 게 좋다.

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

const unionParent = (parent, a, b) => {
  const n1 = getParent(parent, a);
  const n2 = getParent(parent, b);
  if(n1 < n2) return parent[n2] = n1;
  else return parent[n1] = n2;
}

const findParent = (parent, a, b) => {
  const n1 = getParent(parent, a);
  const n2 = getParent(parent, b);
  if(n1 === n2) return true;
  else return false;
}

function solution(n, costs) {
  let answer = 0;
  // 부모를 자기 자신으로 초기화하고 시작한다.
  const parent = new Array(n).fill().map((_,i) => i)
  // const parent = [];
  // for(let i = 0; i < n; i++) parent.push(i);

  // 간선을 기준으로 오름차순 정렬 
  costs.sort((a, b) => a[2] - b[2]);
  
  // 크루스칼 알고리즘 
  for(const cost of costs) {
    // cost[0]과 cost[1]의 부모가 같지 않으면 (== 같은 그래프가 아니면)
    if(!findParent(parent, cost[0], cost[1])) {
      answer += cost[2]; // 연결 비용 합산 
      // 유니온파인드 알고리즘 
      unionParent(parent, cost[0], cost[1]); // 같은 그래프로 연결을 해준다. 
    }
  }
  
  return answer;
}

다른 풀이 2

function solution(n, costs) {
  costs.sort((a,b) => a[2] - b[2]);
  let [from, to, answer] = costs.shift();
  let connected = new Set([from, to]);
  while (connected.size < n) {
      let index = costs.findIndex(([from, to]) =>
                                  // 순환(사이클)이 생기지 않아야 하므로,
                                  // 한쪽이 연결되면 다른 한쪽은 연결되지 않은 경우만 찾는다. 
                                  connected.has(from) && !connected.has(to)
                                  || connected.has(to) && !connected.has(from)
                                 );

      let [[from, to, cost]] = costs.splice(index, 1);
      answer += cost;
      connected.add(from).add(to);
  }
  return answer;
}