1446 swift / c++ - 지름길

다이나믹프로그래밍과 다익스트라 두 방법 모두 사용할 수 있습니다.

 

시간 복잡도

• 시간 복잡도는 O(D + N)입니다.
  • D는 고속도로의 길이, N은 지름길의 수입니다.
  • 문제에서 N ≤ 12, D ≤ 10,000이므로, 이 접근 방식은 충분히 효율적입니다.

 

C++ DP 풀이.

#include <bits/stdc++.h>

using namespace std;

#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, d;
  cin >> n >> d;

  vector<pair<int, int>> graph[10001];

  for (int i = 0; i < n; i++) {
    int from, to, cost;
    cin >> from >> to >> cost;
    if (to <= d) {
      graph[from].push_back({to, cost});
    }
  }

  vector<int> dist(d + 1, INF);

  dist[0] = 0;

  for (int i = 0; i <= d; i++) {
    if (i > 0) {
      dist[i] = min(dist[i], dist[i - 1] + 1);
    }

    for (auto& g : graph[i]) {
      int next = g.first;
      int cost = g.second;
      if (dist[next] > dist[i] + cost) {
        dist[next] = dist[i] + cost;
      }
    }
  }

  cout << dist[d];

  return 0;
}

import Foundation

let nd = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, d) = (nd[0], nd[1])

var graph = [[(Int, Int)]](repeating: [], count: d + 1)

for _ in 0..<n {
    let shortcut = readLine()!.split(separator: " ").map{Int(String($0))!}
    let from = shortcut[0], to = shortcut[1], cost = shortcut[2]
    if to <= d {
        graph[from].append((to, cost))
    }
}

var dist = [Int](repeating: Int.max, count: d + 1)
dist[0] = 0

for i in 0...d {
    if i > 0 {
        dist[i] = min(dist[i], dist[i - 1] + 1)
    }
    
    for (next, cost) in graph[i] {
        if next <= d {
            dist[next] = min(dist[next], dist[i] + cost)
        }
    }
}

print(dist[d])

다익스트라 알고리즘과 DP의 차이점

• 동적 계획법 (DP) 방식은 각 지점에서 순차적으로 거리를 갱신하면서 최단 거리를 찾습니다. 이 방식은 모든 지점을 방문하며 각 지름길을 업데이트하는 방식으로 구현됩니다.
• 다익스트라 알고리즘은 우선순위 큐를 사용하여 현재 최단 거리가 작은 지점부터 탐색합니다. 따라서 최적의 경로를 더 빨리 찾기 위한 탐색 순서의 최적화가 가능합니다.
• 이 문제에서 두 방법 모두 사용이 가능하지만, 다익스트라 알고리즘은 일반적으로 더 많은 정점이 존재하고 가중치가 다양한 경우 더 효율적으로 작동합니다.

시간 복잡도

• 다익스트라 알고리즘의 시간 복잡도는 O((V + E) * log V)입니다.
  • V는 정점의 개수 (D), E는 간선의 개수 (N)입니다.
  • 우선순위 큐를 사용하는 경우, 각 정점 및 간선의 업데이트가 로그 시간에 수행됩니다.
• 이 문제에서는 N ≤ 12, D ≤ 10,000이기 때문에, 다익스트라의 시간 복잡도는 충분히 효율적입니다.

결론

• DP 방식과 다익스트라 알고리즘 모두 이 문제에서 사용될 수 있습니다.
• DP 방식은 각 위치에서 가능한 모든 경로를 반복적으로 갱신하는 방식이며, 다익스트라 알고리즘은 우선순위 큐를 사용하여 현재 가능한 최단 경로를 효율적으로 찾아갑니다.
• 다익스트라 방식은 더 많은 정점과 간선이 있을 때 효율적으로 작동하며, 우선순위 큐를 사용하여 최적의 정점을 빠르게 선택합니다.

c++ 다익스트라 풀이

#include <bits/stdc++.h>

using namespace std;

#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, d;
  cin >> n >> d;

  vector<pair<int, int>> graph[10001];

  for (int i = 0; i < n; i++) {
    int from, to, cost;
    cin >> from >> to >> cost;
    if (to <= d) {
      graph[from].push_back({to, cost});
    }
  }

  // 다익스트라를 위한 최소 힙 선언 (거리, 정점) 형태로 저장
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      pq;

  // 최단 거리 배열 초기화
  vector<int> dist(d + 1, INF);
  dist[0] = 0;
  pq.push({0, 0});  // (거리, 시작 위치)

  // 다익스트라 알고리즘
  while (!pq.empty()) {
    int currentDist = pq.top().first;
    int currentNode = pq.top().second;
    pq.pop();

    // 이미 처리된 거리보다 큰 경우는 무시
    if (currentDist > dist[currentNode]) {
      continue;
    }

    // 직선 도로로 이동 (다음 1km)
    if (currentNode + 1 <= d && dist[currentNode + 1] > currentDist + 1) {
      dist[currentNode + 1] = currentDist + 1;
      pq.push({dist[currentNode + 1], currentNode + 1});
    }

    // 현재 노드에서 출발하는 지름길 처리
    for (auto& shortcut : graph[currentNode]) {
      int nextNode = shortcut.first;
      int shortcutCost = shortcut.second;

      if (dist[nextNode] > currentDist + shortcutCost) {
        dist[nextNode] = currentDist + shortcutCost;
        pq.push({dist[nextNode], nextNode});
      }
    }
  }

  cout << dist[d] << "\n";
  return 0;
}

Swift Priority Queue

struct Heap<T> {
    var elements: [T] = []
    let priorityFunction: (T, T) -> Bool
    
    init(priorityFunction: @escaping (T, T) -> Bool) {
        self.priorityFunction = priorityFunction
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    func peek() -> T? {
        return elements.first
    }
    
    mutating func remove() -> T? {
        guard !elements.isEmpty else {
            return nil
        }
        if elements.count == 1 {
            return elements.removeFirst()
        } else {
            let value = elements.first
            elements[0] = elements.removeLast()
            siftDown(elementAtIndex: 0)
            return value
        }
    }
    
    mutating func push(_ element: T) {
        elements.append(element)
        siftUp(elementAtIndex: elements.count - 1)
    }
    
    mutating func pop() -> T? {
        guard !isEmpty else {
            return nil
        }
        elements.swapAt(0, elements.count - 1)
        let poppedElement = elements.removeLast()
        siftDown(elementAtIndex: 0)
        return poppedElement
    }
    
    private mutating func siftUp(elementAtIndex index: Int) {
        let parent = parentIndex(of: index)
        guard !isRoot(index), priorityFunction(elements[index], elements[parent]) else {
            return
        }
        elements.swapAt(index, parent)
        siftUp(elementAtIndex: parent)
    }
    
    private mutating func siftDown(elementAtIndex index: Int) {
        let childIndex = highestPriorityIndex(for: index)
        if index == childIndex {
            return
        }
        elements.swapAt(index, childIndex)
        siftDown(elementAtIndex: childIndex)
    }
    
    private func isRoot(_ index: Int) -> Bool {
        return index == 0
    }
    
    private func leftChildIndex(of index: Int) -> Int {
        return 2 * index + 1
    }
    
    private func rightChildIndex(of index: Int) -> Int {
        return 2 * index + 2
    }
    
    private func parentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }
    
    private func highestPriorityIndex(for parent: Int) -> Int {
        let leftChild = leftChildIndex(of: parent)
        let rightChild = rightChildIndex(of: parent)
        
        var highest = parent
        if leftChild < elements.count && priorityFunction(elements[leftChild], elements[highest]) {
            highest = leftChild
        }
        if rightChild < elements.count && priorityFunction(elements[rightChild], elements[highest]) {
            highest = rightChild
        }
        return highest
    }
}

Swift 다익스트라

let nd = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, d) = (nd[0], nd[1])

var graph = [[(Int, Int)]](repeating: [], count: d + 1)

for _ in 0..<n {
    let shortcut = readLine()!.split(separator: " ").map{Int(String($0))!}
    let from = shortcut[0], to = shortcut[1], cost = shortcut[2]
    if to <= d {
        graph[from].append((to, cost))
    }
}

var dist = [Int](repeating: Int.max, count: d + 1)
dist[0] = 0

var pq = Heap<(Int, Int)>(priorityFunction: {$0.0 < $1.0})
pq.push((0, 0))

while !pq.isEmpty {
    let (currentDist, currentNode) = pq.pop()!
    
    if currentDist > dist[currentNode] {
        continue
    }
    
    if currentNode + 1 <= d && dist[currentNode + 1] > currentDist + 1 {
        dist[currentNode + 1] = currentDist + 1
        pq.push((dist[currentNode + 1], currentNode + 1))
    }
    
    for (nextNode, cost) in graph[currentNode] {
        if dist[nextNode] > currentDist + cost {
            dist[nextNode] = currentDist + cost
            pq.push((dist[nextNode], nextNode))
        }
    }
}

print(dist[d])