문제

https://www.acmicpc.net/problem/1916

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

• Line 1: 도시의 개수 N(1 ≤ N ≤ 1,000)
• Line 2: 버스의 개수 M(1 ≤ M ≤ 100,000)
• Line 3 ~ M+2: 버스정보 [ 출발도시, 도착도시, 코스트]
• Line M+3: [출발도시, 도착도시]

출력

출발도시 ~ 도착도시까지 가는데 드는 최소비용을 출력하라.

Try1

풀이방법

예전에 배웠던 다익스트라 알고리즘으로 해결을 시도했다.
논리상으로는 완벽하다고 생각했던 풀이법이었는데 틀렸다고 나오니 갑갑했다.

// cost 최대값
const MAX_COST = 1000001;
// 노드 개수
const N = +input();
// 간선 개수
const M = +input();
// 가중치 그래프
const G = Array.from({length: N}, (_,i) => 
    Array.from({length: N}, (_,j) => i===j ? 0 : MAX_COST
));
const visited = Array(N).fill(false);
let graph = [];

// 가중치 그래프 초기화
for (let i=0; i<M; i++) {
    const [start, end, cost] = input();
    // 시작 ~ 끝 코스트
    G[start-1][end-1] = cost;
}
const [start,end] = input();

// 현재 배열에서 최소값을 찾음
// 조건1. 방문하지 않은 노드
// 조건2. 자신의 노드 제외
const findMinIdx = function() {
    let min = MAX_COST;
    let idx = 0;

    for (let i=0; i<N; i++) {
      // 방문하지 않았을 경우
        if ( !visited[i] && min > graph[i]) {
            min = graph[i];
            idx = i;
        }
    }
  //값이 제일 작은 노드의 인덱스 반환
    return idx;
}
// 다익스트라 알고리즘
const dijkstra = function(nowIdx) {
    graph = [...G[nowIdx]];
    visited[nowIdx] = true;

    while(1) {
      	// 모든 노드를 방문했다면 while문 탈출
        if (visited.every( visit => visit === true)){
            return;
        }
        nowIdx = findMinIdx();
        visited[nowIdx] = true;
        
        for (let i=0; i<N; i++) {
          	// i노드까지 가는데 드는 기존비용
            const originDist = graph[i];
          	// i노드까지 가는데 드는 새로운 비용
            const plusDist =   graph[nowIdx] + G[nowIdx][i];
          	// 새롭게 계산한 비용이 기존 비용보다 낮을경우
            if (plusDist < originDist) {
              	// graph[i]의 비용 갱신
                graph[i] = plusDist;
            }
        }
    }
}
dijkstra(start-1);
console.log(graph[end-1]);

Catch1

알고리즘 자체에는 문제가 없었다.
하지만 문제를 다시 읽어보니 반례가 존재할 가능성이 있었다.
세번째 줄부터 입력되는 값(간선)은 같은 간선에 여러개가 입력될 수 있다.
그래서

1 2 0
1 2 10
1 2 5

와 같은식으로 입력된다면 가장 마지막에 입력된 5가 G[1-1][2-1]에 입력된다.

Finally1

1. 가중치 그래프를 초기화 하는 부분에서 조건을 추가해준다.
   • 기존에 그냥 값을 그대로 넣는 방식에서
     Math.min(원래값, 새로운값) 을 비교해 넣어준다.

Try2

풀이방법

기존의 그래프를 초기화 하는 방법을 아래처럼 바꿔줬다.

기존방식

for (let i=0; i<M; i++) {
    const [start, end, cost] = input();
    // 시작 ~ 끝 코스트
    G[start-1][end-1] = cost;
}

바꾼방식

for (let i=0; i<M; i++) {
    const [start, end, cost] = input();
    // 시작 ~ 끝 코스트
    G[start-1][end-1] = Math.min(cost, G[start-1][end-1]);
}

Catch2

예상대로 반례가 존재했었다.
깔끔하게 문제를 해결했지만 또 다른 문제가 있었다.
이번에는 시간초과가 나온다.
아마도 findMinIdx 함수가 모든 배열을 탐색해서 시간초과가 나오는것같다.

Finally2

단순 배열이 아니라 최소힙을 사용하면 문제가 풀릴것같다.

Try 3

풀이방법

위에서 생각했던대로 우선순위큐를 사용해 문제를 해결했다.
하지만 풀면서 예상치 못한 반례가 존재했는데 아래에서 설명하겠다.
자바스크립트에는 기본적으로 힙을 지원 안해줘서 최소힙부터 만들었다.

 interface HeapArr<T> {
    node: T,
    val: number
}
 class Heap<T> {
    private arr: HeapArr<T>[];

    constructor() {
        this.arr = [];
    }
    
    push(node: T, val: number):void {
        const _node: HeapArr<T> = {
            node,
            val
        }
        this.arr.push(_node);
        this.heapifyUp();
    }
    pop(): HeapArr<T> | undefined {
        const lastIdx = this.getLastIdx();
        let outData: HeapArr<T> | undefined;

        [this.arr[0], this.arr[lastIdx]] = 
            [this.arr[lastIdx], this.arr[0]];

        outData = this.arr.pop();
        this.heapifyDown();
        return outData;
    }
    epmty(): boolean {
        if (this.arr.length === 0) return true;
        else return false;
    }
    head(): HeapArr<T> {
        return this.arr[0];
    }

    private heapifyUp() {
        let idx = this.getLastIdx();
        while (idx > 0) {
            const parent = this.getParent(idx);
            // 최소힙, 부모의 val이 자식보다 작을경우
            if (this.arr[parent].val > this.arr[idx].val) {
                // 구조분해할당으로 두 값을 스왑해줌
                [this.arr[parent], this.arr[idx]] = 
                    [this.arr[idx], this.arr[parent]];
            }
            idx = parent;
        }
    }
    private heapifyDown(){
        const leafIdx = Math.ceil(this.getLastIdx() / 2);
        let idx = 0;
                    
        // 리프노드에 갈 떄 까지 반복.
        while( idx < leafIdx ) {
            const left = this.getLeft(idx);
            const right = this.getRight(idx);
            let minChild: number;

            // 오른쪽에 자식이 있다면 왼쪽, 오른쪽 val중 더 작은쪽이 minChilc
            if (right <= this.getLastIdx()) {
                minChild = this.arr[left].val <= this.arr[right].val
                        ? left
                        : right;
            // 오른쪽에 자식이 없다면 무조건 왼쪽이 minChild
            }else {
                minChild = left;
            }
            // arr[idx]가 arr[minChild]보다 클경우 두개를 교환한다.
            if (this.arr[idx].val > this.arr[minChild].val) {
                [this.arr[idx], this.arr[minChild]] = 
                    [this.arr[minChild], this.arr[idx]];
            }
            // 현재 idx를 변경해준다.
            idx = minChild;
        }
    }
    

    private getParent(idx: number): number {
        return Math.floor((idx-1) / 2);
    }
    private getLeft(idx: number): number {
        return (idx * 2) + 1;
    }
    private getRight(idx: number): number {
        return (idx * 2) + 2;
    }
    private getLastIdx(): number {
        return this.arr.length - 1;
    }
    getArr() {
        return this.arr;
    }
}

최소힙으로 만들면서 방문 확인을 위한 visited와
최소값을 찾기위한 함수는 필요없게 됐다.
visited가 필요 없는 이유는 내가 갔던길은 일단 큐에 넣고보는데
현재 dist에 저장된 cost보다 큐에 저장된 cost가 더 높으면 넘어가기 때문이다.

class MapNode {
    to: number;
    cost: number;

    constructor(to: number, cost: number) {
        this.to = to;
        this.cost = cost;
    }
}

const MAX_COST = Infinity;
const N = +input();//정점 개수
const M = +input();//간선 개수

const G: number[][] = Array.from({length: N}, (_,i) => 
    Array.from({length: N}, (_,j) => i===j ? 0 : MAX_COST
));
const heap = new Heap<MapNode>();
const dist = Array(N).fill(MAX_COST);

// 가중치 그래프 초기ㅘ
for (let i=0; i<M; i++) {
    const [start, end, cost] = input();
    G[start-1][end-1] = Math.min(cost, G[start-1][end-1]);
    // G[end-1][start-1] = Math.min(cost, G[end-1][start-1]);
}
const [start,end] = input();

const dijkstra = function(start: number) {
    dist[start] = 0;
    heap.push(new MapNode(start, 0), 0);

    // 노드에 방문한적 없으면 while문 돌림
    while ( !heap.epmty()) {
        // 현재 노드
        const node = heap.pop()!.node;
        // 현재 노드 비용
        const cost = node.cost;
        // 현재 노드 위치
        const now = node.to;

        // 큐에서 꺼낸 노드의 까지의 거리가
        // 현재 계산된 거리보다 멀경우 그냥 넘김
        if (dist[now] < cost) {
            continue;
        }
        // 해당 배열 순환
        for (let i=0; i<N; i++) {
            // plus = 지금까지 더한 거리 + 이동해야하는 거리
            const plus = dist[now] + G[now][i];
            // 주개를 더한 거리가 기존에 계산했던 거리보다 작으면
            if (plus < dist[i]) {
                // 큐 삽입위한 노드 생성
                const newNode = new MapNode(i, plus);
                // 기존 거리를 새로 더한 거리로 대체
                dist[i] = plus;
                // 큐에 삽입함.
                heap.push(newNode, newNode.cost);
            }
        }
    }

}
dijkstra(start-1);
console.log(dist[end-1]);

풀면서 생겼던 반례들

1. 같은 간선의 다른 값이 입력될 때 나중에 입력된 값만 인식해서 생기는 문제도 있었다.
2. MAX_COST를 10000001로 설정했었는데 만약 10000000이 여러번 더해지면 문제가 생긴다.