[BOJ] 1753 최단 경로 js

📦 문제

[백준] 1753 문제링크

💡 가중치는 10 이하의 자연수이다.
💡 주어진 시작점.

시작점이 주어진다는 걸 잊으면 안된다!
예제입력이 1로 시작해서 시작점을 고정해서 여러번 해맸다..ㅜ

⚡️ 풀이

처음에 bfs로 풀어봤는데 ..ㅎ 너무 생각이 없었던 것 같다
가장 작은 값을 찾아서 방문 가능한 정점까지의 가중치를 최솟값으로 업데이트하는 방법으로 선택했다
음의 가중치 값이 10 이하 자연수로 알려져있어서 다익스트라를 사용해서 풀었다
[나무위키] 다익스트라

다음에 방문할 작은 정점을 찾고

const getIdx = () => {
    let min = Infinity;
    let idx = 0;
    for (let i = 0; i < V; i++){
        if (!visit[i] && min > weight[i]){
            idx = i;
            min = weight[i];
        }
    }
    return idx;
}

간선을 탐색하며 가중치를 업데이트해준다.

const dijk = (s) => {
    weight[s] = 0;
    for (let i = 0; i < V; i++){
        const cur = getIdx();
        visit[cur] = 1;
        for (const [nxt, w] of graph[cur]) {
            if (weight[cur] + w < weight[nxt]){
                weight[nxt] = weight[cur] + w;
            }
        }
    }
}

[github] 1753 전체 코드