Portfolio

문제

풀이

효성

첫 번째 풀이 - `실패..`


function solution(n, costs) {
    
    const board = new Array(n).fill().map(_ => new Array(n).fill(Infinity));
  
    for(let i = 0; i < n; i++) {
    	board[i][i] = 0;
    }
    
    costs.forEach(pos => {
        const [a, b, cost] = pos;
        board[a][b] = cost;
        board[b][a] = cost;
    });
    
    let answer = 0;
    let visited = Array(n).fill(false);
    
    const checkConnect = () => {
        let returnCnt = n - 1;
        for(let i=0; i<n; i++) {
            if(visited[i]) {
                returnCnt--;
            }
        }
        return returnCnt === 0 ? true : false;
    }
    
    for(let i = 0; i < n; i++) {
        let min = Infinity, minIdx = [];
        for(let j = 0; j < n; j++){
            if(checkConnect()) {
			    			return answer;
            }
            if(board[i] === board[j]){
                continue;
            }
            if(board[i][j] < min) {
		        		min = board[i][j];
                minIdx.push(i, j);
            }
        }
        if(board[minIdx[0]][minIdx[1]] === board[minIdx[0]][minIdx[1]]) {
            visited[minIdx[0]] = true;
            visited[minIdx[1]] = true;
            answer += min;
        }        
    }
}

참고한 풀이


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 = [];
  for(let i = 0; i < n; i++) {
    parent.push(i);
  }
  costs.sort((a, b) => a[2] - b[2]);
  
  for(const cost of costs) {
    if(!findParent(parent, cost[0], cost[1])) {
      answer += cost[2];
      unionParent(parent, cost[0], cost[1]);
    }
  }
  
  return answer;
}

재영


class MinHeap {
  constructor() {
    this.heap = [null];
    this.size = 0;
  }
  heappush(val) {
    this.heap.push(val);
    let nowIndex = this.heap.length - 1;
    let parentIndex = this.updateParentIndex(nowIndex);
    while (nowIndex > 1 && this.heap[nowIndex][0] < this.heap[parentIndex][0]) {
      this.swap(nowIndex, parentIndex);
      nowIndex = parentIndex;
      parentIndex = this.updateParentIndex(nowIndex);
    }
    this.size += 1;
  }
  heappop() {
    this.size -= 1;
    const min = this.heap[1];
    this.heap[1] = this.heap.pop();
    let [nowIndex, leftIndex, rightIndex] = this.updateIndices(1);
    if (!this.heap[leftIndex]) return min;
    if (!this.heap[rightIndex]) {
      if (this.heap[leftIndex][0] < this.heap[nowIndex][0]) {
        this.swap(nowIndex, leftIndex);
      }
      return min;
    }
    while (
      this.heap[rightIndex] !== undefined && 
      this.heap[leftIndex] !== undefined && 
      (this.heap[leftIndex][0] < this.heap[nowIndex][0] ||
        this.heap[rightIndex][0] < this.heap[nowIndex][0])
    ) {
      const minIndex =
        this.heap[leftIndex][0] <= this.heap[rightIndex][0]
          ? leftIndex
          : rightIndex;
      this.swap(nowIndex, minIndex);
      [nowIndex, leftIndex, rightIndex] = this.updateIndices(minIndex);
    }
    return min;
  }

  updateParentIndex(nowIndex) {
    return Math.floor(nowIndex / 2);
  }
  updateIndices(nowIndex) {
    return [nowIndex, nowIndex * 2, nowIndex * 2 + 1];
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

const findParent = (x, parent) => {
  return parent[x] === x ? x : findParent(parent[x], parent);
};

const updateParent = (a, b, parent) => {
  const parentA = findParent(a, parent);
  const parentB = findParent(b, parent);
  if (parent[parentA] < parent[parentB]) {
    parent[parentB] = parent[parentA];
  } else if (parent[parentB] < parent[parentA]) parent[parentA] = parent[parentB];
};

const solution = (n, costs) => {
  let result = 0;
  let cnt = 1;
  const minHeap = new MinHeap();
  const parent = Array.from({ length: n }, (_, idx) => idx);
  costs.forEach(([from, to, cost]) => minHeap.heappush([cost, from, to]));
  while (minHeap.size) {
    const [cost, from, to] = minHeap.heappop();
    if (findParent(from, parent) !== findParent(to, parent)) {
      updateParent(from, to, parent);
      cnt += 1;
      result += cost;
      if (cnt === n) break;
    }
  }
  return result;
};

은찬


const unionFind = (n, parent) => {
    if(parent[n] === n){
        return n;
    }
    
    return parent[n] = unionFind(parent[n], parent);
}

const solution = (n, costs) => {
    let answer = 0;
    
    const parent = Array(n).fill(0);
    
    for(let i = 0; i < n; i++){
        parent[i] = i;
    }
    
    costs.sort((a, b) => a[2] - b[2]);
    
    for(let i = 0; i < costs.length; i++){
        const start = unionFind(costs[i][0], parent);
        const end = unionFind(costs[i][1], parent);
        const cost = costs[i][2];
        
        if(start !== end){
            answer += cost;
            parent[start] = end;
        }
    }
    
    return answer;
}

섬 연결하기

문제

풀이

첫 번째 풀이 - 실패..

참고한 풀이

첫 번째 풀이 - `실패..`