[Swift] BOJ 1753 최단경로

BOJ 1753 최단경로

 

✅ 다익스트라 알고리즘의 가장 대표적인 문제였음.

근데 나 못품 ..ㅎ

다익스트라 알고리즘은 맞았는데 자꾸 시간초과가 나는거임.

근데 나중에 알고보니까 자료구조 힙을 사용하지 않아서더러군 !_!

그래서 다른 사람 알고리즘 기반으로 학습하기로 함. 여기서 시간 너무 잡아먹길래,, 아니면 힙부터 하고 다시 돌아와야지.

 

✅ 내 코드 - 시간초과

struct b1753 {
    static func run() {
        // 입력부
        let firstLine = readLine()!.split(separator: " ").map( {Int(String($0))! })

        let secondLine = Int(readLine()!)!
        
        var table = [Int](repeating: Int(1e9), count: firstLine[0]+1)
        var graph = [Int: [Int: Int]]()
        
        for i in 1...firstLine[0] {
            graph[i] = [:]
        }
        
        for _ in 0..<firstLine[1] {
            let info = readLine()!.split(separator: " ").map { Int($0)! }
            
            let start = info[0]
            let end = info[1]
            let weight = info[2]
            
            var temp = graph[start]!
            
            if temp[end] == nil {
                temp[end] = weight
            } else {
                temp[end] = min(temp[end]!, weight)
            }
            graph[start] = temp
        }
        
        // 구현부 - 다익스트라 알고리즘을 구현합니다.
        
        var priorityQueue = [(Int, Int)]()
        
        var visited = [secondLine] // 방문한 노드
        table[secondLine] = 0
        
        graph[secondLine]!.forEach {
            
            priorityQueue.append(($0.key,$0.value))
        }
        
        priorityQueue = priorityQueue.sorted { $0.1 > $1.1 }
        
        var popNode = secondLine
        while !priorityQueue.isEmpty {
            
            // 테이블 업데이트
            priorityQueue.forEach { (node, weight) in
                if !visited.contains(node) {
                    table[node] = min(table[node], weight + table[popNode])
                }
                
            }
            
            // 우선순위 큐 업데이트 -> 다음 작업을 위함.
            popNode = priorityQueue.last!.0
            visited.append(popNode)
            priorityQueue.removeAll()
            
            graph[popNode]?.forEach{
                priorityQueue.append(($0.key,$0.value))
            }
            priorityQueue = priorityQueue.sorted { $0.1 > $1.1 }
            
        }
        
        // 출력부
        table[1...].forEach {
            if $0 == Int(1e9) {
                print("INF")
            } else {
                print($0)
            }
        }
    }
}

 

 

✅ 정답코드 - 출처는 제일 아래에 있습니다.

import Foundation

struct PriorityQueue<T> {
  var array = [T]()
  let sort: (T, T) -> Bool

  init(sort: @escaping (T, T) -> Bool) {
    self.sort = sort
  }

  var isEmpty: Bool {
    return array.isEmpty
  }

  var count: Int {
    return array.count
  }

  func peek() -> T? {
    return array.first
  }

  func leftChildIndex(ofParentAt index: Int) -> Int {
    return (2 * index) + 1
  }

  func rightChildIndex(ofParentAt index: Int) -> Int {
    return (2 * index) + 2
  }

  func parentIndex(ofChildAt index: Int) -> Int {
    return (index - 1) / 2
  }

  // MARK:- remove operation
  mutating func pop() -> T? {
    guard !isEmpty else {
      return nil
    }

    array.swapAt(0, count - 1)
    defer {
      siftDown(from: 0)
    }
    return array.removeLast()
  }

  mutating func siftDown(from index: Int) {
    var parent = index
    while true {
      let left = leftChildIndex(ofParentAt: parent)
      let right = rightChildIndex(ofParentAt: parent)
      var candidate = parent

      if left < count && sort(array[left], array[candidate]) {
        candidate = left
      }
      if right < count && sort(array[right], array[candidate]) {
        candidate = right
      }
      if candidate == parent {
        return
      }
      array.swapAt(parent, candidate)
      parent = candidate
    }
  }

  // MARK:- insert operation
  mutating func push(_ element: T) {
    array.append(element)
    siftUp(from: array.count - 1)
  }

  mutating func siftUp(from index: Int) {
    var child = index
    var parent = parentIndex(ofChildAt: child)
    while child > 0 && sort(array[child], array[parent]) {
      array.swapAt(child, parent)
      child = parent
      parent = parentIndex(ofChildAt: child)
    }
  }
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = Int(readLine()!)!
let v = input[0], e = input[1]
let INF = Int(1e9)

var edges = [[(Int, Int)]](repeating: [(Int, Int)](), count: v + 1)

for _ in 0..<e {
  let i = readLine()!.split(separator: " ").map { Int(String($0))! }
  edges[i[0]].append((i[1], i[2]))
}

var dist = [Int](repeating: INF, count: v + 1)
var pq = PriorityQueue<(Int, Int)>(sort: { $0.1 < $1.1 })

dist[k] = 0
pq.push((k, 0))

while !pq.isEmpty {
  let (now, cost) = pq.pop()!

  if cost > dist[now] {
    continue
  }

  for (next, w) in edges[now] {
    if dist[now] + w <= dist[next] {
      dist[next] = dist[now] + w
      pq.push((next, dist[next]))
    }
  }
}

for i in 1...v {
  if dist[i] < INF {
    print(dist[i])
  } else {
    print("INF")
  }
}

 

 

 

 

 

(출처)

https://github.com/skyqnaqna/algorithm_study/blob/main/boj/Dijkstra/BOJ_1753.swift#L8

GitHub - skyqnaqna/algorithm_study: 알고리즘 문제 코드 기록