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

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

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

코드

function solution(n, costs) {
    costs.sort((a, b) => a[2] - b[2]); //비용 순서대로 정렬
    let nodes = Array(n).fill()
    console.log(costs)
    for (let i of costs) {
        if (!nodes[i[0]]) {
            nodes[i[0]] = [i[1]]
        }
        else {
            nodes[i[0]].push(i[1])

        }
        if (!nodes[i[1]]) {
            nodes[i[1]] = [i[0]]
        }
        else {
            nodes[i[1]].push(i[0])

        }
    }

    console.log(nodes);

    //크루스칼 알고리즘 사용
    let t = Array(n).fill(), tv = [], cyclechk=[false];

    for (let i = 0; i < costs.length; i++) {
        dfs(t, costs[i][0], costs[i][1], cyclechk)//사이클 찾기
        if (cyclechk[0]) { //사이클일 경우
            cyclechk[0] = false;
            continue;
        }
        let par = Math.min(costs[i][0], costs[i][1])
        let chi = Math.max(costs[i][0], costs[i][1])

        console.log(par, chi)
        if(!t[par]){
            t[par] = [chi];
        }
        else if (!t[par].includes(chi)) {
            t[par].push(chi);
        }
        console.log()
        console.log('t')
        console.log(t)
        tv.push(costs[i])
    }

    console.log();
    console.log(tv);

    return tv.reduce((prev, curr) => {
        return prev + curr[2];
    }, 0)
}

function dfs(nodes, start, end, cyclechk, visited){    


    if(nodes.length <= 1){ //더 갈 곳 없으면 중단시키기
        cyclechk[0] = false;
        return;
    }

    if(nodes[start].includes(end)){ //end로 가는 다른 길 있으면 중단시키기
        cyclechk[0] = true;
        return;
    }


    for(let i of nodes[start]){
        if(cyclechk[0]){ //사이클 식별하면 재귀함수 중단시키기
            return;
        }

        dfs(nodes.filter((x, idx)=>idx!=nodes.indexOf(start)), i, end, cyclechk)//다음 노드 방문해서 확인하기
    }
}

크루스칼 알고리즘으로 최소비용트리를 만들려고 했다. 그런데 사이클 찾는 dfs 함수에서 문제가 발생했는데 오류를 찾을 수가 없어서 챗지피티님께 여쭤봤다.

2차원 배열 선언에서

    Array(n).fill()

로 선언을 했는데 이렇게하면 undefined가 들어가서 위에서 if문을 통해서 걸러냈는데 Array.from 문을 통해서 바로 빈 2차원 배열을 만들 수 있게 됐다.

dfs함수에서 indexOf를 통해서 방문한 노드를 제거하는 방식을 선호했고 이전 다른 문제에서도 이용하고 그랬는데

'RangeError : Maxmum call stack size exceeded'

오류가 발생했는데 visited 배열을 사용하는 것을 추천해줘서 그 방식으로 바꿨다.

function solution(n, costs) {
    costs.sort((a, b) => a[2] - b[2]); //비용 순서대로 정렬
    let nodes = Array.from({length: n}, () => [])
    // console.log(costs)
    for (let i of costs) {
        nodes[i[0]].push(i[1])
        nodes[i[1]].push(i[0])
    }

    console.log(nodes);

    //크루스칼 알고리즘 사용
    let t = Array(n).fill(), tv = [], cyclechk=[false];

    for (let i = 0; i < costs.length; i++) {
        dfs(nodes, costs[i][0], costs[i][1], cyclechk, [])//사이클 찾기
        console.log(cyclechk)
        if (cyclechk[0]) { //사이클일 경우
            cyclechk[0] = false;
            continue;
        }
        let par = Math.min(costs[i][0], costs[i][1])
        let chi = Math.max(costs[i][0], costs[i][1])

        console.log(par, chi)
        if(!t[par]){
            t[par] = [chi];
        }
        else if (!t[par].includes(chi)) {
            t[par].push(chi);
        }
        // console.log()
        // console.log('t')
        // console.log(t)
        tv.push(costs[i])
    }

    // console.log();
    // console.log(tv);

    return tv.reduce((prev, curr) => {
        return prev + curr[2];
    }, 0)
}

function dfs(nodes, start, end, cyclechk, visited) {
    if (visited[start]) {
        return;
    }

    visited[start] = true;

    if (start === end) {
        cyclechk[0] = true;
        return;
    }

    for (let i of nodes[start]) {
        if (!cyclechk[0]) {
            dfs(nodes, i, end, cyclechk, visited);
        }
    }
}

챗지피티의 조언을 참고해서 코드를 수정했는데 제대로 작동하지 않았다.
사이클이 아니더라도 start에서 end로 가는 길이 있으면 사이클로 인식해서 멈추는 것이 문제였다.

 function solution(n, costs) {
    costs.sort((a, b) => a[2] - b[2]); //비용 순서대로 정렬
    let nodes = Array.from({length: n}, () => [])
    for (let i of costs) {
        nodes[i[0]].push(i[1])
        nodes[i[1]].push(i[0])
    }


    //크루스칼 알고리즘 사용
    let kgraph = Array.from({length: n}, () => []), tv = [], cyclechk=[false];

    for (let i = 0; i < costs.length; i++) {
        if(kgraph[costs[i][0]]){
            dfs(kgraph, costs[i][0], costs[i][1], cyclechk, [])//사이클 찾기
        }
        if (cyclechk[0]) { //사이클일 경우
            cyclechk[0] = false;
            continue;
        }
        let par = Math.min(costs[i][0], costs[i][1])
        let chi = Math.max(costs[i][0], costs[i][1])

        // 크루스칼로 그래프 만들기
        kgraph[par].push(chi)
        kgraph[chi].push(par)

        tv.push(costs[i])
    }

    return tv.reduce((prev, curr) => {
        return prev + curr[2];
    }, 0)
}

function dfs(nodes, start, end, cyclechk, visited) {
    if(cyclechk[0]){
        return;
    }

    if (visited[start]) {
        return;
    }

    visited[start] = true;

    if (start == end){
        cyclechk[0] = true;
        return;
    }

    for (let i of nodes[start]) {
        if (!cyclechk[0]) {
            dfs(nodes, i, end, cyclechk, visited);
        }
    }
}

예전에 만들었던 코드라 잘못 이해 하고 있었다.
kgraph가 크루스칼 알고리즘으로 찾은 노드를 넣는 역할이었는데 착각했다.
아무것도 없을 때는 일단 가장 작은 값을 가진 엣지를 찾아서 노드 두 개 넣고 시작했고, 그 뒤로는 dfs 돌리면서 이제 사이클을 찾게 했다.

dfs는 코드 짧게 하려고 필터링 안 하고 그냥 visited 배열 써야겠다.