문제 링크

프로그래머스 문제

풀이

처음 문제를 보자마자 든 생각은 dfs를 통해서 모든 노드가 가능한 edge를 연결한 후, 그중 비용이 가자 적었던 경우를 골라내는것이 옳다는 생각이 들었다.
하지만 이 경우 100^100 이라는 막대한 테스트 케이스가 발생하므로 무제가 있다고 판단했다.

하지만 결국 제대로 된 알고리즘을 구하지 못하고 풀이를 찾아보게 되었다.

다른 문제 풀이 를 찾게 되어 이 코드를 이해하게 되었다.

하지만 unionfind 방식또한 있으므로 참고하는것이 필요하다고 생각했다.

코드

const solution = (n, costs) => {
  let answer = 0;
  const isVisited = new Array(n).fill(false);
  const isBridge = new Array(costs.length).fill(false);
  //비용이 작은 간선을 순서로 정렬
  costs.sort((a, b) => {
    return a[2] - b[2];
  });
  let num = 0;

  //처음에 가장 작은 간선을 무조건 넣는다. 비용이 가장작으므로
  isVisited[costs[0][0]] = true;
  isVisited[costs[0][1]] = true;
  isBridge[0] = true;
  answer += costs[0][2];
  num += 1;

  //간선의 개수가 노드의 개수-1을 만족할때까지 순회한다.
  while (num < n - 1) {
    for (let i = 1; i < costs.length; i++) {
      const [start, end, cost] = costs[i];
      //다리가 건설되어 있지않고 한쪽노드만 방문한경우를 찾는다.
      if (
        !isBridge[i] &&
        ((!isVisited[start] && isVisited[end]) ||
          (isVisited[start] && !isVisited[end]))
      ) {
        num++;
        answer += cost;
        isVisited[start] = true;
        isVisited[end] = true;
        isBridge[i] = true;
        break;
      }
      console.log(isVisited);
    }
  }
  return answer;
};