Portfolio

📄문제

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.

위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다.그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 타고 귀가하려고 합니다. A의 집은 6번 지점에 있으며 B의 집은 2번 지점에 있고 두 사람이 모두 귀가하는 데 소요되는 예상 최저 택시요금이 얼마인 지 계산하려고 합니다.

그림의 원은 지점을 나타내며 원 안의 숫자는 지점 번호를 나타냅니다.

지점이 n개일 때, 지점 번호는 1부터 n까지 사용됩니다.

지점 간에 택시가 이동할 수 있는 경로를 간선이라 하며, 간선에 표시된 숫자는 두 지점 사이의 예상 택시요금을 나타냅니다.

간선은 편의 상 직선으로 표시되어 있습니다.
위 그림 예시에서, 4번 지점에서 1번 지점으로(4→1) 가거나, 1번 지점에서 4번 지점으로(1→4) 갈 때 예상 택시요금은 10원으로 동일하며 이동 방향에 따라 달라지지 않습니다.

예상되는 최저 택시요금은 다음과 같이 계산됩니다.

4→1→5 : A, B가 합승하여 택시를 이용합니다. 예상 택시요금은 10 + 24 = 34원 입니다.
5→6 : A가 혼자 택시를 이용합니다. 예상 택시요금은 2원 입니다.
5→3→2 : B가 혼자 택시를 이용합니다. 예상 택시요금은 24 + 22 = 46원 입니다.
A, B 모두 귀가 완료까지 예상되는 최저 택시요금은 34 + 2 + 46 = 82원 입니다.

[문제]

지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

✏️풀이

은찬


const solution = (n, s, a, b, fares) => {
    // answer와 cost를 무조건 크게 만들어서 최소값 찾기
    let answer = 999999999;
    const cost = Array.from({length: n + 1}, () => Array(n + 1).fill(999999999));
    
    // i -> i로 오는 경우는 0으로 리셋
    for(let i = 1; i <= n; i++){
        cost[i][i] = 0;
    }
    
    // A -> B 의 비용 저장
    for(let i = 0; i < fares.length; i++){
        const A = fares[i][0];
        const B = fares[i][1];
        const fare = fares[i][2];
        
        cost[A][B] = fare;
        cost[B][A] = fare;
    }
    
    // 플로이드 와샬
    // i -> j 로 갈 때, i -> k -> j 로 가는 경우의 비용이 더 싼 경우 갱신
    for(let k = 1; k <= n; k++){
        for(let i = 1; i <= n; i++){
            for(let j = 1; j <= n; j++){
                cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
    
    // 두 사람이 i 까지 합승한 후, i에서 각자의 도착지로 가는 비용을 구하여 answer와 비교 및 갱신
    for(let i = 1; i <= n; i++){
        answer = Math.min(answer, cost[s][i] + cost[i][a] + cost[i][b]);
    }
    
    return answer;
}

효성


function solution (n, s, a, b, fares) {
  const board = new Array(n).fill().map(_ => new Array(n).fill(Infinity));
  
  for(let i = 0; i < n; i++) {
    board[i][i] = 0;
  }
  fares.forEach(pos => {
    const [x, y, weight] = pos;
    board[x-1][y-1] = weight;
    board[y-1][x-1] = weight;
  });
  
	// k는 경유노드, i는 시작노드, j는 도착노드
  for(let k = 0; k < n; k++) {
    for(let i = 0; i < n; i++) {
      for(let j = 0; j < n; j++) {
        if(board[i][j] > board[i][k] + board[k][j])
          board[i][j] = board[i][k] + board[k][j];
      }
    }
  }
  
  let answer = board[s-1][a-1] + board[s-1][b-1];
  for(let i = 0; i < n; i++) {
    const shortest = board[s-1][i] + board[i][a-1] + board[i][b-1];
    answer = Math.min(answer, shortest);
  }
  
  return answer;
}

합승 택시 요금

📄문제

문제 설명

[문제]

✏️풀이