[그리디] 프로그래머스 '섬 연결하기' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

2. 코드

우선 최소 비용이 되어야하므로 비용 순 오름차순 정렬한다 => 그리디에서 매우 중요! 처음엔 이 부분을 간과했다. 그래서 막혔나보다. 그 다음, 가장 적은 비용의 간선 부터 연결해 나가면서 불필요하게 중복 연결되어 사이클을 형성시키는 간선을 연결하지 않는다(순환방지). 중요한 것은 이전에 연결한 섬들과 연결 가능한 섬들부터 쭉 연결해나간다는 것이다. 

ex) 5, [[0, 1, 1], [3, 4, 1], [1, 2, 2], [2, 3, 4]]

while문 안에 for문 두고, while문이 반복되면서 계속 for문에서 i는 0부터 시작하는 이유가 뭘까?
비용 별 오름차순 정렬 후 0,1 섬 연결한 다음 순서가 3,4 섬인 관계로 이 순서는 잠시 넘어갔다가 0과 1과 관련된 섬 먼저 연결 후에 다시 돌아와서 따져줘야한다. 만약 for문 하나만 사용하여 따져준다면 3,4 섬 순서는 넘어가고 다시 돌아오지 않아 이 경우를 따져줄 수가 없다.

function solution(n, costs) {
    let answer = 0;
    costs.sort((a,b)=>a[2]-b[2]); //비용이 작도록 정렬 
    const vis = new Array(n).fill(0); // 방문 여부
    const bridge = new Array(costs.length).fill(0); // 다리 연결 여부
    //다리 연결의 시작(비용 가장 적은 다리)
    vis[costs[0][0]] = true;
    vis[costs[0][1]] = true;
    answer += costs[0][2];
    bridge[0] = 1;
    let cnt = 1; // 다리 수 
    // 처음 연결한 섬과 연결가능한 섬들부터 하나하나 연결해나가는 방식
    while(cnt < n-1){ // 간선의 수 === 노드 갯수 -1 (모든 노드가 연결되는 시점)
        for(let i=0;i<costs.length;i+=1){
            const [start,end,cost] = costs[i];
            if(bridge[i]) continue; //이미 연결된 경우라면 넘어감
            // 둘 중 하나는 연결되었지만 하나는 연결안됨 -> 미연결 섬과 연결가능한 섬들을 연결해나가면 됨
            if(!vis[start] && vis[end] ||vis[start] && !vis[end]){
                cnt += 1; //다리 연결 + 1
                vis[start] = 1;
                vis[end] = 1;
                bridge[i] = 1;
                answer += cost;
                break; // while문 조건 확인하고 for문 돌며 다음 case 검사하려고 break  
            }
        }
    }
    return answer;
}

처음에는 큐로 풀기 시도했다가 최소 거리 비교가 안되는 것 같아 정답을 보고 이해했다. 그래도 레벨3 풀이법 중에 가장 정답에 가깝게 접근했던 것 같아 뿌듯했다.

+ 왜 레벨3인지 정확히 이해가는 문제...쉽지 않다 쉽지않아

 

복기

4/12