[JavaScript] 백준 1446 : 지름길

level : silver 1
문제링크 : 지름길

1446번: 지름길

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N,D] = input.shift().split(' ').map(Number);
input = input.map(arr=>arr.split(' ').map(Number));

function solution(n,d,graph){
    let answer = d;

    // graph를 temp로 deep copy
    let temp = JSON.parse(JSON.stringify(graph));
    
    // 시작 위치, 도착 위치, 지름길의 길이 순서로 오름차순 정렬
    temp.sort((a,b)=> a[0] === b[0] ? (a[1] === b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0]);
    
    let matrix = new Map();
    
    for(let i = 0; i < n; i++){
        let min = matrix.get(temp[i][1])??temp[i][1];
        
        if(min > d)
            continue;
        
        min = Math.min(min, temp[i][0] + temp[i][2]);
        
        for(let [key, value] of matrix)
            if(key <= temp[i][0])
                min = Math.min(min, (temp[i][0] - key) + value + temp[i][2]);
        
        matrix.set(temp[i][1],min);
    }

    for(const [key, value] of matrix)
        answer = Math.min(answer, d - key + value);
    
    return answer;
}

console.log(solution(N,D,input));

풀이방법
가장 긴 거리는 그대로 가는 거리인 d이다. answer를 d로 초기화한다.

graph를 deep copy하여 temp를 생성한다. (JavaScript는 function에서 Array를 받으면 call by reference이기에 본래의 Array를 변형 시킬수 없는 경우를 생각하여 deep copy를 하였다.)

temp를 sort메서드를 이용하여 시작 위치, 도착 위치, 지름길의 길이 순서로 오름차순 정렬한다.

matrix라는 Map Object를 생성하여 각 위치에 대한 최솟값을 넣을 예정이다.

min은 각 위치에서 가장 작은 값을 나타내는 값이다.
i번째 도착 위치에 대한 값을 key로하는 matrix값으로 min을 초기화하고 만약 없다면 도착 위치로 min값을 초기화한다.
만약 min값이 최동 도착지인 d보다 크면 continue한다.(이는 도착 위치가 최종 위치보다 더 먼 지점일 경우를 pass하기 위해서다.)

min과 (시작 위치 + 지름길의 길이) 중 작은 값을 min에 넣는다.

matrix에서 key와 value를 꺼내며 key가 시작 위치이하인 경우 min값과 key값을 거쳐 도착 위치까지 오는 경위의 길이를 비교하여 작은 값을 min값에 넣는다.

matrix에 key를 도착위치, value를 min으로 세팅한다.

이후 반복문이 종료되면 matrix를 기반으로 가장 짧은 거리를 계산하여 answer에 집어 넣고 return 한다.

느낀점
ES2020에 추가된 Nullish Coalescing Operator(??)를 알게되어 처음 써보았는데 굉장히 편리하다는 생각이 들었다.
다른 스펙도 추가되었는데 아직 써본적이 적다.
기회가 된다면 공부하는 것을 바로바로 적용해보아야겠다.