[Programmers] 합승 택시 요금

문제

 

2021 KAKAO BLIND RECRUITMENT > 합승 택시 요금

코딩테스트 연습 - 합승 택시 요금

 

 

아이디어

 

이 문제는 문제를 보자마자 플로이드-워셜을 이용해야겠다는 생각이 났던 문제입니다.

 

왜냐하면 무지와 어피치가 합승했다가 흩어지는 경우에서 합승이 끝나는 정점의 위치는 모든 정점이 해당될 수 있기 때문입니다.

 

결과적으로 모든 정점에 대해 다른 정점까지의 최소 거리가 필요했고 그래프에서 모든 정점 간의 최소 거리를 구하는 플로이드-워셜이 생각났습니다.

 

플로이드-워셜이 생각난 순간 풀이를 위한 아이디어는 간단했습니다.

 

1. 플로이드-워셜로 정점간 최소 거리 구하기

2. s→a, s→b가 겹치지 않을 때 최소 거리 구하기

3. 모든 정점을 순회하며 해당 정점까지 합승하고 흩어지는 최소 거리 구하기

 

 

구현 코드 (JavaScript)

 

function solution(n, s, a, b, fares) {
    const array = Array.from(Array(n), () => new Array(n).fill(Number.MAX_VALUE)); // 최대값으로 배열 초기화

    for(let i=0; i<fares.length; i++) {
        const fare = fares[i];
        array[fare[0]-1][fare[1]-1] = array[fare[1]-1][fare[0]-1] = fare[2]; // 좌표값을 배열에 저장
    }

    for(let i=0; i<n; i++) {
        array[i][i] = 0; // 자기위치로 돌아오는 값은 0
    }

    for(let k=0; k<n; k++) { // 플로이드-워셜 알고리즘
        for(let i=0; i<n; i++) {
            if(i === k) {
                continue;
            }

            for(let j=0; j<n; j++) {
                if(j === i || j === k) {
                    continue;
                }

                if(array[i][k] !== Number.MAX_VALUE && array[k][j] !== Number.MAX_VALUE) { // i→k, k→j로 가는 길이 있을 경우
                    array[i][j] = Math.min(array[i][j], array[i][k] + array[k][j]);
                }
            }
        }
    }

    let res = array[s-1][a-1] + array[s-1][b-1]; // s→a와 s→b가 겹치는 길이 없을 경우
    for(let i=0; i<n; i++) {
        // s→i까지 합승하고 i→a, i→b 따로 갈 경우
        if(array[s-1][i] !== Number.MAX_VALUE && array[i][a-1] !== Number.MAX_VALUE && array[i][b-1] !== Number.MAX_VALUE) {
            res = Math.min(res, array[s-1][i] + array[i][a-1] + array[i][b-1]);
        }
    }

    return res;
}

 

 

읽어주셔서 감사합니다.