[프로그래머스] 2021Kakao > 합승 택시 요금 - 자바스크립트

programmers.co.kr/learn/courses/30/lessons/72413

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

---

[ 아이디어 ]

최단 경로를 구하는 것임으로 다익스트라 or 플로이드 와샬 알고리즘으로 처리

단순한 최단경로가 아니므로 모든 경로에 대한 값이 필요할 듯하여 플로이드 와샬로 결정

해당 알고리즘으로 모든 경로의 값을 채움특정 노드(장소)에서 A집, B집, 출발지(S)의 합 가장 작은게 정답
-> 어느 지점에서 합승하든 말든 상관없다는 마인드, 어찌됬건 A,B,S의 모든 지점을 찍어야함으로 존재하는 모든 장소로부터 3개가 연결되는 값의 최소값을 구하면 된다.

[ 코드 ]

function solution(n, s, a, b, fares) {
  //지점 크기만큼 2차원 배열 및 자기자신 0으로 변경
  let pathMap = Array.from(Array(n), () => new Array(n).fill(Infinity));
  pathMap = pathMap.map((item, index) => {
    let temp = [...item];
    temp[index] = 0;
    return temp;
  });

  // 요금 채우기
  fares.forEach(([from, to, fee]) => {
    pathMap[from - 1][to - 1] = fee;
    pathMap[to - 1][from - 1] = fee;
  });

  //플루이드 와셜 알고리즘, 모든 경로 최소값 찾기
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        pathMap[i][j] = Math.min(pathMap[i][j], pathMap[i][k] + pathMap[k][j]);
      }
    }
  }

  //합승 최소 요금 찾기
  let answer = Infinity;
  for (let i = 0; i < n; i++) {
    answer = Math.min(answer, pathMap[s - 1][i] + pathMap[a - 1][i] + pathMap[b - 1][i]);
    console.log(pathMap[s - 1][i] + pathMap[a - 1][i] + pathMap[b - 1][i]);
  }

  return answer;
}

---

[ 각 코드에 따른 pathMap ]

//input
solution(6, 4, 6, 2, [
    [4, 1, 10],
    [3, 5, 24],
    [5, 6, 2],
    [3, 1, 41],
    [5, 1, 24],
    [4, 6, 50],
    [2, 4, 66],
    [2, 3, 22],
    [1, 6, 25],
  ])

 

  
  지점 크기만큼 2차원 배열 및 자기자신 0으로 변경
  [
    [ 0, Infinity, Infinity, Infinity, Infinity, Infinity ],
    [ Infinity, 0, Infinity, Infinity, Infinity, Infinity ],
    [ Infinity, Infinity, 0, Infinity, Infinity, Infinity ],
    [ Infinity, Infinity, Infinity, 0, Infinity, Infinity ],
    [ Infinity, Infinity, Infinity, Infinity, 0, Infinity ],
    [ Infinity, Infinity, Infinity, Infinity, Infinity, 0 ]
  ]
  요금 채우기
  [
    [ 0, Infinity, 41, 10, 24, 25 ],
    [ Infinity, 0, 22, 66, Infinity, Infinity ],
    [ 41, 22, 0, Infinity, 24, Infinity ],
    [ 10, 66, Infinity, 0, Infinity, 50 ],
    [ 24, Infinity, 24, Infinity, 0, 2 ],
    [ 25, Infinity, Infinity, 50, 2, 0 ]
  ]
  플루이드 와셜 알고리즘, 모든 경로 최소값 찾기
  [
    [ 0, 63, 41, 10, 24, 25 ],
    [ 63, 0, 22, 66, 46, 48 ],
    [ 41, 22, 0, 51, 24, 26 ],
    [ 10, 66, 51, 0, 34, 35 ],
    [ 24, 46, 24, 34, 0, 2 ],
    [ 25, 48, 26, 35, 2, 0 ]
  ]
  

 

---

[ 팁 ]

fares.forEach(([from, to, fee]) => {
  pathMap[from - 1][to - 1] = fee;
  pathMap[to - 1][from - 1] = fee;
});

코드 중간에 이러한 배열메소드가 있다. 

본래라면 [N,N,N]으로 이루어진 배열인 item를 받고 배열에 index로 접근하여 사용한다.

  fares.forEach((item) => {
    pathMap[item[0] - 1][item[1] - 1] = item[2];
    pathMap[item[1] - 1][item[0] - 1] = item[2];
  });

하지만 ES6의 비구조화 할당 문법을 이용해 item를 [from, to, fee]로 분해하여 가져왔다. 이를 통해서 

item[0], item[1], item[2]처럼 의미를 알수없는 값이 아닌 from, to, fee 라는 변수로 가져와 바로 활용할 수 있게 되었다.

[자바스크립트] 구조 분해 할당(destructuring assignment)에 대하여

 

[자바스크립트]JS다운 코드 스타일 #4. 비구조화 할당

 

---

[ 가볼 만한 사이트 ]

아래 사이트는 경로 알고리즘을 시각적으로 확인할수 있는 사이트다. 마우스를 통해 벽을 세우고 파란->빨간점으로 가는 최단경로를 구하는 방식을 보여준다. 한번 들어가서 확인해보는 것도 좋다.

PathFinding.js