Dijkstra Algorithm

[dlehdanakf]

개요

• 그래프에서 특정 노드에 대해 다른 노드까지 가는 최단거리, 최소하중을 구하는 알고리즘
• 원래는 시간복잡도 O(N²) 이고, 우선순위큐를 사용하면 O(N log N) 까지도 가능하다는데 일단 시간복잡도가 높은 것 부터 이해해보자.

예제

배달

• 문제 바로가기
• 1번 노드에서 다른 노드까지 최소하중을 모두 구한 뒤 K 보다 같거나 낮은 하중값으로 갈 수 있는 노드들의 개수만 구해주면된다.
• 다익스트라 알고리즘을 사용하면 쉽게 구할 수 있다.

다익스트라 알고리즘

• 모든 노드를 방문하지 않은 상태로 만든다.
• 시작할 노드를 선택한다. 문제에선 1번 노드가 될 것이다.
• 1번 노드에서 Edge가 연결된 모든 노드를 찾는다
• Edge 들 중에서 이미 방문하지 않은 노드는 일반 방문하고, 방문했던 노드에 대해서는 지금까지 가중치 + 이번 엣지 가중치가 더 작을 경우 방문한다.

function solution(N, road, K) {
    const nodes = new Array(N + 1).fill(Infinity);
    nodes[0] = nodes[1] = 0;

    const traverse = (_n, _w) => {
        nodes[_n] = _w;
        road
            .filter(([n1, n2]) => n1 === _n || n2 === _n)
            .map(([n1, n2, w]) => n1 === _n ? [n2, w] : [n1, w])
            .forEach(([n, w]) => {
                if(_w + w < nodes[n]) {
                    traverse(n, _w + w);
                }
            });
    };

    traverse(1, 0);
    return nodes.filter(e => e <= K).length - 1;
}

[dlehdanakf]

가장 먼 노드

• 문제 바로가기
• 다익스트라 알고리즘을 사용하진 않았지만 그래프 탐색 문제이기도 하고, 처음에 다익스트라로 접근하다 런타임 에러 문제를 마주쳤었어서 짤막하게 정리해본다.
• 1번 노드에서 거리가 가장 먼 노드를 구하고, 해당 노드와 같은 거리에 있는 노드의 개수를 구하면 되는 간단한 문젠데도 애먹었다...ㅡㅡ

해결과정

• 처음에는 1번 노드부터 DFS 탐색을 이어가며 엣지를 통과할 때 마다 가중치를 1씩 추가하는 방식으로 문제를 풀었다.
• 하지만 테스트케이스 7,8,9에서 런타임에러, 아마도 스택오버플로우가 발생한 것 같다.
• 문제를 자세히보면 엣지의 최대 개수가 많은데 그래프 탐색을 하다보면 오버플로우가 발생하는 모양이었다.
• 너비 탐색으로 풀면 되지 않을까 아이디어를 내봤다.
• 위 사진에서 1번 노드에 연결되어있는 노드는 2, 3번 노드이고, 2,3번 노드에 연결되어있는 노드는 1,2,3,4,5,6번 노드이다.
• 중복을 제거하면 4,5,6번 노드만 남겠다.
• 아니, 사실 중복을 제거하는 문제가 아니라 2,3번 노드를 방문하는 가중치 1 보다 큰 가중치를 가진 상태인 노드는 4,5,6만 남을 것이다.
• 이런 식으로 가중치를 +1씩 증가해 나아가며 3 가중치일 때 방문할 수 있는 노드에 대해 파악해 나아가면 재귀함수 코드를 작성하지 않더라도 문제를 해결할 수 있다.
• 사진에서도 보다시피 2와 3 노드에서 모두 4 노드를 갈 수 있으므로 traversal 과정에서 노드가 분명 중복될 것이다. 이 문제를 해결하기 위해 Set 객체를 사용한다.
• 가중치가 가장 큰 노드(가장 먼 노드)의 개수를 구하는 문제였으므로, 이전까지 계속해서 노드의 개수를 카운트하다 더 이상 방문할 노드가 없는 단계에서 카운트하던 수를 return 하기만 하면 최대의 수를 구하는 시간비용을 절약할 수 있다.

function solution(n, edge) {
    const nodes = new Array(n + 1).fill(n + 1);
    const map = new Array(n + 1).fill(null).map(_ => []);
    nodes[0] = nodes[1] = 0;
    edge.forEach(([a,b]) => { map[a].push(b), map[b].push(a) });

    let arr = new Set([1]), weight = 1, answer = 0;
    while(true) {
        arr = new Set([...arr].map(e => map[e]).flat().filter(e => weight < nodes[e]));
        if(arr.size === 0) {
            return answer;
        }

        arr.forEach(e => nodes[e] = weight);
        answer = arr.size;
        weight += 1;
    }
}

• 프로그래머스 다른사람 풀이를 보더라도 내가 작성한 코드가 제일 간결해보인다 후후