[프로그래머스 lev3/JS] 합승 택시 요금

문제 출처

프로그래머스 lev3 - 합승 택시 요금

나의 풀이 (실패)

삽질을 해보았다.

합승과 혼자를 구분하기 위해 재귀를 돌면서 한 단계씩 재귀에 진입하기 전에 a,b 두곳에 도착할 수 있는 경로인지를 우선 판단해줬다. a,b 두 곳에 도착할 수 있는 경로인 경우 answer를 업데이트해줘서 최소값을 찾으려 했으나. 당연히 스택 공간이 부족해진다. 시간초과도 당연해 보인다..

그래프 개념이 아직 많이 부족하다.

function solution(n, s, a, b, fares) {
  let answer = Number.MAX_SAFE_INTEGER

  function to(cur, trg, fare, flag, arr){
    if(cur === trg) {
      return [fare, true]
    }

    for(let i=0; i<fares.length; i++){
      const [c, d, f] = fares[i]
      if(cur === c && !arr.includes(d)){
        to(d, trg, fare+f, flag, arr)
      } else if(cur === d && !arr.includes(c)){
        to(c, trg, fare+f, flag, arr)
      }
    }
    return [fare, false]
  }

  function dfs(srt, arr, sum){
    if(srt === a || srt === b) return 

    for(let i=0; i<fares.length; i++){
      const [c, d, f] = fares[i]
      if(srt === c && !arr.includes(d)){
        const [fare1, flag1] = to(d, a, 0, false, [d])
        const [fare2, flag2] = to(d, b, 0, false, [d])

        if(flag1 && flag2){
          answer = Math.min(answer, (fare1 + fare2 + sum))
        } else {
          dfs(d, [...arr, d], sum+f)
        }

      } else if(srt === d && !arr.includes(c)){
        const [fare1, flag1] = to(c, a, 0, false, [c])
        const [fare2, flag2] = to(c, b, 0, false, [c])

        if(flag1 && flag2){
          answer = Math.min(answer, (fare1 + fare2 + sum))
        } else {
          dfs(c, [...arr, c], sum+f)
        }
      }
    }
  }
  dfs(s, [s], 0)
}

다른 풀이 - Floyd-Warshall

// 1
i부터 j까지의 연결 정보와 가중치를 담은 그래프 연결리스트를 생성해준다.
const distance = Array.from(new Array(n), () => new Array(n).fill(9900000))

// 2
자기 자신에 대한 최단 경로는 0이므로

• 1과 2를 같이 하려면 이렇게 해도 된다. const graph = [...new Array(n)].map((_, row) => [...new Array(n)].map((__, column) => (row === column ? 0 : Infinity)) )

// 3
최단 경로 알고리즘을 사용하는데,
모든 정점에서 각 정점으로의 최단 경로(최소 요금)을 구할 때는 dp를 사용하는 플로이드-와샬을 사용하는 게 좋다고 한다. 그래서 앞에서 생성한 그래프 연결리스트를 dp 배열로 업데이트해준다.

// 4
k는 경유노드, i는 시작노드, j는 도착 노드라는 개념을 3중 for문으로 구현해준다. i에서 j까지의 경로에서 k라는 경유노드 개념을 통해 플로이드-와샬 알고리즘을 구현한다.

// 5

function solution (n, s, a, b, fares) {
  // 1
  const board = new Array(n).fill().map(_ => new Array(n).fill(Infinity));
  console.log(board)
  
  // 2
  for(let i = 0; i < n; i++) 
    board[i][i] = 0;
  
  // 3
  fares.forEach(pos => {
    // x에서 y로 가는 최단 경로(최소 요금) = weight 
    const [x, y, weight] = pos;
    board[x-1][y-1] = weight;
    board[y-1][x-1] = weight;
  });
  console.log(board)
  
  // 4
  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];
      }
    }
  }
  
  // 5
  // 초기값은 두 사람이 시작점에서 따로 각각의 목적지로 가는 경우로 설정한다.
  let answer = board[s-1][a-1] + board[s-1][b-1];
  
  for(let i = 0; i < n; i++) {
    // 중간 경유지 i를 거쳐서 각자의 목적지로 가는 경우를 shortest 변수로 설정한 뒤, 따로 가는 것과 i까지 같이 가서 따로 가는 경우를 비교해 최소 요금을 탐색한다. 
    const shortest = board[s-1][i] + board[i][a-1] + board[i][b-1];
    answer = Math.min(answer, shortest);
  }
  
  return answer;
}

console.log(
  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 - Dijkstra

플로이드 와샬 알고리즘은,
동적계획법(dp)를 사용해 그래프에서 가능한 모든 정점 쌍에 대해 최단 거리를 구하는 알고리즘이다. 음의 가중치가 있어도 사용할 수 있고, 많은 수의 간선으로 이루어져 있는 밀집 그래프에 사용하기 적합하다.

다익스트라 알고리즘은,
일반적으로 단일 정점 간 최단 거리 산출 시에 자주 사용한다. 즉, 다익스트라가 특정 시작지점 A에서 나머지 정점들로의 최단 거리를 구하기에 적합하다면, 플로이드-와샬은 모든 정점 간의 최단 거리를 구하기 때문에 한번 구해놓으면 편하다는 장점이 있다.

이 문제는 시작 지점이 주어지며, 무방향 그래프(a->b와 b->a는 같다)이므로 다익스트라 알고리즘을 사용하는 게 속도면에서 더 빠르다.

function solution(n, s, a, b, fares) {
  let answer = Infinity

  // 연결 그래프 생성 
  const g = [...Array(n+1)].map(() => [...Array(n+1)].map(() => Infinity))
  for(let i=1; i<=n; i++) g[i][i]=0
  fares.forEach(([start, end, dist]) => {
    g[start][end] = g[end][start] = dist
  })
  
  // 출발지점(s)와 도착지점(a,b)을 모두 출발지점으로 사용한다. 
  const distFromA = dijkstra(n, g, a)
  const distFromB = dijkstra(n, g, b)
  const distFromS = dijkstra(n, g, s)

  for(let i=1; i<=n; i++){
    // if(distFromS[i] === Infinity || distFromA[i] === Infinity || distFromB[i] === Infinity) continue
    answer = Math.min(answer, distFromS[i] + distFromA[i] + distFromB[i])
  }
  return answer

}

function dijkstra(n, graph, node) { // 정점 개수, graph, 출발 정점

  const visit = [...Array(n+1)].map(() => false)

  // let lastVisit = node // 출발지점
  let dist = [...graph[node]] // 출발지점에서 인접 노드들까지 거리 배열 
  visit[node] = true // 출발 노드 방문 처리

  for(let k=1; k<=n-2; k++){
      
    let min = Infinity // 선택하지 않은 노드 중 가장 가까운 인접 노드 찾기.
    let index = 0

    for(let i=1; i<=n; i++){
      if(min > dist[i] && !visit[i]){
        min = dist[i]
        index = i
      }
    }
    visit[index] = true
    
    for(let i=1; i<=n; i++){
      if(!visit[i]){
        if(dist[i] > dist[index] + graph[index][i]){
          dist[i] = dist[index] + graph[index][i]
        }            
      }
    }
  }
  return dist
}

참고

[프로그래머스] LV.3 합승 택시 요금 (JS)
[프로그래머스] 합승 택시 요금 - 2021 카카오 채용 (c++)