[코딩테스트]백준 - 최단경로(1753)

문제

최단경로(1753)

해결한 코드

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let VE = input[0].split(' ')
let v = +VE[0]
let startV = +input[1]
let uvws = []
for (let i = 2; i < input.length; i++) {
    uvws.push(input[i].split(' ').map((e) => +e))
}

let linkedInfo = (uvws) => {
    let links = Array(v + 1)
    uvws.forEach((edge) => {
        if (!links[edge[0]]) links[edge[0]] = []
        links[edge[0]].push({
            vertex: edge[1],
            cost: edge[2]
        })
    })
    return links
}

class MinHeap {
    constructor() {
        this.nodes = []
    }

    insert(value) {
        this.nodes.push(value)
        this.bubbleUp()
    }

    bubbleUp(index = this.nodes.length - 1) {
        if (index < 1) return;

        const currentNode = this.nodes[index]
        const parentIndex = Math.floor((index - 1) / 2)
        const parentNode = this.nodes[parentIndex]
        if (parentNode.cost <= currentNode.cost) return;

        this.nodes[index] = parentNode
        this.nodes[parentIndex] = currentNode
        index = parentIndex
        this.bubbleUp(index)
    }

    extract() {
        const min = this.nodes[0]
        if(this.nodes.length === 1){
            this.nodes.pop();
            return min;
        };
        this.nodes[0] = this.nodes.pop()
        this.trickleDown();
        return min
    }

    trickleDown(index = 0) {
        const leftChildIndex = 2 * index + 1
        const rightChildIndex = 2 * index + 2
        const length = this.nodes.length
        let minimum = index

        if(!this.nodes[rightChildIndex] && !this.nodes[leftChildIndex]) return;
        if(!this.nodes[rightChildIndex]){
            if(this.nodes[leftChildIndex].cost < this.nodes[minimum].cost){
                minimum = leftChildIndex;
            }
            return;
        }

        if(this.nodes[leftChildIndex].cost > this.nodes[rightChildIndex].cost){
            if (rightChildIndex <= length && this.nodes[rightChildIndex].cost < this.nodes[minimum].cost) {
                minimum = rightChildIndex
            }
        }else{
            if (leftChildIndex <= length && this.nodes[leftChildIndex].cost < this.nodes[minimum].cost) {
                minimum = leftChildIndex
            }
        }

        if (minimum !== index) {
            let t = this.nodes[minimum]
            this.nodes[minimum] = this.nodes[index]
            this.nodes[index] = t
            this.trickleDown(minimum)
        }
    }
}

let dijkstra = (links, startV) => {
    let shortestPathTable = Array(v + 1).fill(Infinity)
    shortestPathTable[0] = -1
    shortestPathTable[startV] = 0
    let minHeap = new MinHeap()
    const start = {
        vertex: startV,
        cost: 0
    };
    minHeap.insert(start);
    while (minHeap.nodes.length) {
        const selected = minHeap.extract();
        const startVertex = selected.vertex,
            beforeCost = selected.cost;
        if (links[startVertex] === undefined) continue;
        if (shortestPathTable[startVertex] < beforeCost) continue;
        links[startVertex].forEach((edge) => {
            const {
                vertex,
                cost
            } = edge
            if (shortestPathTable[vertex] <= shortestPathTable[startVertex] + cost) return;
            shortestPathTable[vertex] = shortestPathTable[startVertex] + cost
            const next = {
                vertex,
                cost: shortestPathTable[startVertex] + cost
            };
            minHeap.insert(next)
        })
    }
    return shortestPathTable
}

let printAll = (shortestPathTable) => {
    let answer = ''
    for (let i = 1; i < shortestPathTable.length; i++) {
        if (shortestPathTable[i] === Infinity) answer += 'INF' + '\n'
        else answer += shortestPathTable[i] + "" + '\n'
    }
    console.log(answer.trim())
}

let links = linkedInfo(uvws);
let table = dijkstra(links, startV)
printAll(table)

풀이

1. 힙을 사용한다.

입력으로 들어오는 데이터 개수가 많기 때문에 힙을 사용하지 않으면 시간초과가 난다.

• 최소 힙을 구현한다.
• 비용에 따라 배치한다.
  • 부모노드는 자식노드보다 비용이 더 작다.

2. 다익스트라 알고리즘을 사용한다.

• 최단거리 테이블을 만든다.
• 힙에서 값을 하나씩 빼며 거리를 계산한다.

가장 먼저, 최단거리 테이블에서 시작정점에 해당하는 index와 cost를 힙에 삽입한다.

2-1. 최단거리 테이블의 index, cost 값과 힙에서 뺀 vertex, cost값을 비교하여

• 힙에서 뺀 vertex가 연결된 정점이 없으면 continue
• 힙에서 뺀 cost가 최단거리 테이블의 cost보다 크면 continue
• 힙에서 뺀 vertex를 거쳐갈 때 cost가 같거나 더 커지면 continue
• 그렇지 않으면 해당 vertex를 거쳐갈 때의 cost를 최단거리 테이블의 cost로 바꾼다.

2-2. 최단거리 테이블에서 값이 바뀐 애들을 힙에 삽입한다.

2-3. 위 과정을 힙의 길이가 0이 될때까지 반복한다

3. 최단거리 테이블 내 cost들을 출력한다.

놓쳤던 부분

• 힙 사용
  내가 힙을 제대로 구현하지 못했었다... 그래서 힙 공부의 필요성을 절감함
• continue
  • 정점에 연결된 간선이 없으면
  • 힙에서 꺼낸 정점의 비용이 최단거리 테이블 내 같은 정점의 비용보다 크면
  • 새로운 비용을 더한 값이 최단거리 테이블의 비용보다 크면
  바로바로 무시해주어야 시간초과에 걸리지 않는다.