72413. 합승 택시 요금

프로그래머스 72413번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 스쿨

풀이

아이디어

아이디어 도출

무방향이고 가중치가 있는 그래프에서 최단거리를 구하는 문제이다! 특정 시작점이 존재하는 것을 보니 아무리 봐도 다익스트라 알고리즘을 사용하는 문제이다.

핵심은 어디까지 합승을 하느냐의 문제이다. 합승을 끝내는 지점을 c라고 했을 때, 전체 비용은 아래와 같이 표현할 수 있다.

// (s → c) + (c → a) + (c → b)
dist(s, c) + dist(c, a) + dist(c, b)

합승을 하지 않아도 괜찮기 때문에 시작점이 c가 되어도 된다. 즉 모든 노드 c를 합승 분기점 후보로 두고, 위 식의 최솟값을 구하면 되는 문제였다.

알고리즘 결정

처음에는 다익스트라 알고리즘을 쓰면 되겠다고 생각했지만 합승 분기점이라는 또 다른 출발점이 생겼고, 이 출발점 후보는 모든 노드이기에 플로이드-워셜 알고리즘을 써야 하나? 하는 생각도 들었다. 하지만 약간 생각을 바꾸면 다익스트라 알고리즘만으로도 문제를 풀 수 있고, 이 편이 더 효율적이다.

다익스트라 3번

• distS = dijkstra(s) : s에서 출발하는 경로의 최단거리
• distA = dijkstra(a) : a에서 출발하는 경로의 최단거리
• distB = dijkstra(b) : b에서 출발하는 경로의 최단거리

어차피 무방향이기 때문에 c → a 경로나 a → c 경로나 비용은 동일하다. 따라서 a, b에서 출발하는 경로의 최단 거리를 구한 다음에, 모든 c 후보를 검토하면서 최단 거리를 구해줬다.

let answer = Infinity;
for (let c = 1; c <= n; c++) {
  answer = Math.min(answer, distS[c] + distA[c] + distB[c]);
}

코드

class Heap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }

  size() {
    return this.heap.length;
  }

  // 새로운 원소를 힙에 추가
  // 가장 끝에 넣고 제자리를 찾아서 올려준다.
  push(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1);
  }

  // root를 뺀다.
  // 가장 끝 값을 root로 올리고, 제자리를 찾아 내린다.
  pop() {
    if (this.size() <= 0) return null; // NOTE : 명시적으로 값을 반환해주는 쪽이 더 좋음
    if (this.size() === 1) return this.heap.pop(); // NOTE : 이거 잊지 맙시다.
    const ret = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.siftDown(0);
    return ret;
  }

  // push와 함께 사용
  // 제자리 찾아서 올라가는 단계
  siftUp(idx) {
    // heap 규칙에 어긋난다면 swap으로 올려준다.
    // root이거나 heap 규칙에 잘 맞는다면 shiftUp 중단
    while (idx > 0) {
      const parent = Math.floor((idx - 1) / 2);
      if (this.compare(this.heap[idx], this.heap[parent])) {
        this.swap(idx, parent);
        idx = parent;
      } else {
        break;
      }
    }
  }

  // pop과 함께 사용
  // 제자리 찾아서 내려가는 단계
  siftDown(idx) {
    while (true) {
      const leftChild = idx * 2 + 1;
      const rightChild = idx * 2 + 2;

      let targetChild;
      if (leftChild >= this.size()) break;
      else if (rightChild >= this.size()) targetChild = leftChild;
      else
        targetChild = this.compare(this.heap[leftChild], this.heap[rightChild])
          ? leftChild
          : rightChild;

      if (this.compare(this.heap[targetChild], this.heap[idx])) {
        this.swap(targetChild, idx);
        idx = targetChild;
      } else {
        break;
      }
    }
  }

  // a 인덱스와 b인덱스의 값을 스왑
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

function solution(n, s, a, b, fares) {
  // 0. 다익스트라에 필요한 데이터 준비하기
  // adj: 인접 리스트 (원소: [v, w])
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [c, d, f] of fares) {
    adj[c].push([d, f]);
    adj[d].push([c, f]);
  }

  // 1. 다익스트라 구현
  // start: 경로를 계산할 시작 지점.
  // 시작 지점부터 다른 전체 노드까지의 각 최단 경로를 반환한다.
  function dijkstra(start) {
    // 0) 초기 설정
    const dist = new Array(n + 1).fill(Infinity);
    dist[start] = 0;
    const minHeap = new Heap(([c1, v1], [c2, v2]) => c1 < c2);
    minHeap.push([0, start]);

    // 1) minHeap이 빌 때까지 반복한다.
    while (minHeap.size() > 0) {
      const [cost, u] = minHeap.pop();
      // NOTE : dist 정보와 cost 정보가 다르다면 구버전 정보이므로 넘어간다. (이미 처리한 노드임을 의미)
      if (cost !== dist[u]) continue;
      // 2) u의 간선들을 모두 탐색한다.
      for (const [v, w] of adj[u]) {
        // 3) v로 가는데 걸리는 비용의 최솟값을 업데이트한다.
        const nextCost = cost + w;
        if (nextCost < dist[v]) {
          dist[v] = nextCost;
          minHeap.push([nextCost, v]);
        }
      }
    }

    return dist;
  }

  // 2. S에서 출발하는 경로의 최단거리
  const distS = dijkstra(s);
  // 3. A에서 출발하는 경로의 최단거리 (중간지점 - A까지의 거리 계산용)
  const distA = dijkstra(a);
  // 4. B에서 출발하는 경로의 최단거리 (중간지점 - B까지의 거리 계산용)
  const distB = dijkstra(b);

  // 5. 모든 중간지점 c를 확인하면서 총 비용이 최소가 되는 c를 찾는다.
  // 합승을 안해도 되기 때문에 시작지점도 확인한다.
  let answer = Infinity;
  for (let c = 1; c <= n; c++) {
    answer = Math.min(answer, distS[c] + distA[c] + distB[c]);
  }
  return answer;
}