[CodeKata] 프로그래머스 : 8.8(일), 섬 연결하기

🥋 Oooth More!! (Level 3) : 순위

 

🧮 풀이

graph의 최소값들만 솎아내는 방법을 시도했으나, 모든 노드의 연결여부를 확인할 수 없어 모범답안을 참고했다.

 

🖇 리뷰

function solution(n, costs) {
    let answer = 0,
      island = [],
      bridge = [],
      total = 0;
    costs.sort((a, b) => a[2] - b[2]); // 비용이 낮은 거 순으로 정렬
    island[costs[0][0]] = true; // cost에 제일 앞에 있는 섬 방문 처리 
    island[costs[0][1]] = true; // 
    bridge[0] = true; // 건설된 다리 하나 지어졋다고 친다.  다리 번호 == costs 번호
    answer += costs[0][2]; // 지어진 비용 추가
    total += 1; // 지어진 다리 개수 증가
  
    while (total < n - 1) { // 지어진 다리 개수가 섬개수 -1개 일때, 즉 다리를 다 지었을 때 종료
      for (let i = 1; i < costs.length; i++) { 
        let [start, end, cost] = costs[i]; // 각 코스트별 디스트럭쳐링 
        if (
          !bridge[i] && 
          ((island[start] && !island[end]) || (island[end] && !island[start])) //둘 중 하나만 방문 한 경우 
        ) {
          // 그 다리를 사용한다.
          island[start] = true; 
          island[end] = true;
          bridge[i] = true;
          answer += cost;
          total++;
          break;
        }
      }
    }
  
    return answer;
  }

* 출처 : https://leeyj4805.tistory.com/entry/programmersJavascript-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0

1. isLand는 다리가 건설되어 이어진 섬들을, bridge는 costs의 몇 번째 다리가 지어졌는지, total은 지어진 다리의 총 개수이다.
2. costs를 우선 3번째 인자(비용) 오름차순으로 정렬한다. 비용이 적은 다리부터 확인하기 위함이다.
3. 가장 먼저 출발하는 costs[0] 경우의 노드 costs[0][0], costs[0][1]을 isLand 방문여부를 true로 설정한다.
4. 해당 경우의 bridge도 건설된 것이므로 true 설정한다. 다음으로, answer에 costs[0][2](비용), total에 다리개수 1개를 더한다.
5. 이 total이 n-1개만큼 건설되어야 하므로 이를 while 조건으로 건다. (섬이 5개라면, 다리는 4개만 필요하므로)
6. 다음으로, costs를 순회하며 bridge[i]는 적용되지 않고, 두 섬중 한 곳만 방문한 경우엔 해당 다리를 사용하면 된다.

특별한 알고리즘보다, costs 경우들의 내림차순 정렬과 다양한 조건들(isLand, bridge)의 검사를 통해 풀 수 있는 문제였다.