[프로그래머스] 섬 연결하기 (javascript)

최소 가중치를 먼저 연결하는 문제이다. 크루스칼 알고리즘으로 푸는 사람들도 많다.

나는 다른 방법으로 푸는 걸 참고해서 풀었다. 

순환이 생기지 않기 위해 한 쪽이 방문하면 다른 한쪽은 방문을 안한 경우만 탐사한다.

function solution(n, costs) {
    var answer = 0;
    //비용이 작도록 정렬 
    costs.sort((a,b)=>a[2]-b[2]);
    const vis=new Array(n).fill(false);
    const bridge=new Array(costs.length).fill(false);
    //다리 연결의 시작 
    vis[costs[0][0]]=true;
    vis[costs[0][1]]=true;
    answer+=costs[0][2];
    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]=true;
                answer+=cost;
                break; // break하는 이유: 최대한 가중치가 적은 곳(costs의 앞 부분이 먼저 연결되도록 하기위해서)
                
            }
        }
    }
    return answer;
}