[Refresh ! 코딩 테스트 / js] 게섬 연결하기

문제설명

• 경로를 최소의수로 건널수 있는 걸 찾으시오
• 예전에 풀던 알고리즘 기억이 안나서 새로 다시 공부함
• union find와 크루스칼 의 알고리즘을 더해서 풀었다.

나의 풀이

function solution(n, costs) {

    // union -find 알고리즘이다. 
    let check_parent= new Array(costs.length).fill(0).map((el,index)=>el=index);
    //각각의 index를 채운다. 
    
    const getParent= function(n){
        if (check_parent[n]==n){
            return n;
        }
        return getParent(check_parent[n]);
    }
    const setParent= function(a,b){
         let a_parent= getParent(a);
         let b_parent= getParent(b);
        if(a_parent>b_parent) check_parent[a_parent]=b_parent
        if(a_parent<b_parent) check_parent[b_parent]=a_parent
    }
    // union-find 두개의 함수 생성
    
    costs.sort((a,b)=>a[2]-b[2]);
    //costs으로 간다고 생각
    let answer=0;
    
    for ( var cost of costs){
        let [ to,from,count]= cost;
        //둘이 같은지 안같은지 확인좀
        if(getParent(to) !== getParent(from )){
            answer+=count;
            setParent(to,from);
        }
        
        
    }
    
    
    
    return answer;
    
    
}

• 제귀에서 받아온걸 어떻게 다시 보낼것인가? 부분이 살짝 헷갈렸다.
• 하지만 생각해보면. 받아온걸 바로 보내야되니 . 그부분을 return 값으로 바로 보내는 방법이라는것을 알게 되었다.
• 부모님이 같지 않으면. 연결하는 이유 ? > 이거는 개념 . 부모님이 같지 않다는말이== 아직 연결이 안됬지만. 최소값이야 연결해줘 이말이다. 따라서 이런 상황에서는 answer 값에 road 값을 더하고 연결시켜줬다.

다른 사람 풀이

function getParent(parentArr, point) {
  // 특정 섬의 parent를 반환함
  if (parentArr[point] === point) return point;
  return (parentArr[point] = getParent(parentArr, parentArr[point]));
}
function setParent(parentArr, a, b) {
  // 해당 섬의 parent를 설정함
  const parentA = getParent(parentArr, a);
  const parentB = getParent(parentArr, b);
  if (parentA < parentB) return (parentArr[parentB] = parentA);
  return (parentArr[parentA] = parentB);
}
function solution(n, costs) {
  let answer = 0;
  // 해당 섬들의 parent를 저장하는 배열을 생성함
  let parentArr = Array(n)
    .fill()
    .map((obj, index) => index);
  // 모든 섬의 다리 건설 비용의 오름차순으로 정렬
  costs.sort((a, b) => {
    if (a[2] === b[2]) return a[0] - b[0];
    return a[2] - b[2];
  });
  // 해당 경로를 Union, Find 알고리즘을 활용하여 경로를 찾음
  for (const cost of costs) {
    if (getParent(parentArr, cost[0]) !== getParent(parentArr, cost[1])) {
      answer += cost[2];
      setParent(parentArr, cost[0], cost[1]);
    }
  }
  return answer;
}

내코드와 비교

• 처음에는 그냥 sort 으로 했는데 youtube 에서 같은 값일때는 index 번호가 작은것부터 우선으로 놔둔다고 봐서그렇게 코드를 고쳤다.