[백준] 1753번 최단 경로 [Swift]

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

문제 풀이

이 문제는 다익스트라 알고리즘의 기본적인 형태 입니다.

이 문제에서 제가 겪은 어려움은 시간초과가 발생하는 문제였습니다.

하지만 모든 정점을 확인하는 방법으로 시도하게 되면 시간 초과가 발생하게 되므로

우선 순위 큐를 사용한 다익스트라를 구현해주시면 풀 수 있습니다.

우선 Swift에서는 우선 순위 큐를 기본적으로 제공해주지 않기 때문에 저는 라이노님이 구현해 주신 힙을 사용했습니다.

나중에 이러한 기본 자료구조도 직접 구현해봐야할 것 같아요.

 

다익스트라에 관한 내용은 여기를 봐주시면 되고 이 글에서는 제가 겪은 시간 초과문제에서 배운 점을 써보려고 합니다.

 

1. Swift에서 크기를 정해주지 않은 배열 보다 튜플의 사용이 더 빠르다.

Swift에서 배열은 참조 타입이고 튜플은 값 타입입니다. 

때문에 배열은 메모리의 힙에 저장되고 튜플은 스택에 저장되게 됩니다.

힙은 할당과 해제 비용이 스택보다 크기 때문에 튜플을 사용하는 것이 더 빨랐습니다.

 

여기서 힙에 할당, 해제 비용이 더 큰 이유는 힙에 데이터를 저장하기 위해선 적절한 크기의 공간을 찾고 삽입해야하며 해제할 땐 또 해당 공간을 찾아 해제해줘야합니다. 또한 가장 큰 이유로는 여러개의 쓰레드가 힙에 메모리를 할당할 수 있기 때문에 무결성 보호를 위해 Lock, 동기화 메커니즘 등을 사용해야 한다는 점이었습니다. 

 

실제 이 문제에서 간선의 정보를 [(Int,Int)]형으로 저장한 코드가 [[Int]] 형으로 저장한 코드보다 약 0.300ms 더 빨랐습니다.

하지만 2번 문제가 더 큰 차이를 보였습니다.

 

2. Int(Substring) 보다 Int(String(Substring))이 더 빠르다??

사실 이 문제에서 시간 초과를 만들어낸 근본적인 이유는 이것 때문이었습니다.

문제에 대한 값들을 받는 코드를 처음에 저는 이렇게 작성했습니다.

let firstLine = readLine()!.split(separator: " ").map({Int($0)!})

하지만 실제 통과한 코드는 아래와 같습니다.

let firstLine = readLine()!.split(separator: " ").map({Int(String($0))!})

사실 이는 축약된 클로저로 풀어쓰면 다음과 같이 나타납니다.

// substring -> Int
let firstLine = readLine()!.split(separator: " ").map { (Substring) -> Int in
        return Int(Substring)!
}

// substring -> String -> Int
let firstLine = readLine()!.split(separator: " ").map { (Substring) -> Int in
        return Int(String(Substring))!
}

사실 이 부분이 왜 차이가 나는지는 자세히 모르겠습니다.

공부를 해봐야 할 부분인 것 같아요.

하지만 똑같은 코드에서 이 부분만 수정하면 시간초과문제가 해결되기 때문에... 더 빠를 것으로 예상됩니다.

 

다익스트라라는 부분보다 다른쪽을 더 공부하게된 문제였던 것 같습니다..ㅎㅎ;;;

 

소스 코드

import Foundation


public struct Heap<T> {
  var nodes: [T] = []
  let comparer: (T,T) -> Bool

  var isEmpty: Bool {
      return nodes.isEmpty
  }

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

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

  mutating func insert(_ element: T) {
      var index = nodes.count

      nodes.append(element)

      while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
          nodes.swapAt(index, (index-1)/2)
          index = (index-1)/2
      }
  }

  mutating func delete() -> T? {
      guard !nodes.isEmpty else {
          return nil
      }

      if nodes.count == 1 {
          return nodes.removeFirst()
      }

      let result = nodes.first
      nodes.swapAt(0, nodes.count-1)
      _ = nodes.popLast()

      var index = 0

      while index < nodes.count {
          let left = index * 2 + 1
          let right = left + 1

          if right < nodes.count {
              if comparer(nodes[left], nodes[right]),
                  !comparer(nodes[right], nodes[index]) {
                  nodes.swapAt(right, index)
                  index = right
              } else if !comparer(nodes[left], nodes[index]){
                  nodes.swapAt(left, index)
                  index = left
              } else {
                  break
              }
          } else if left < nodes.count {
              if !comparer(nodes[left], nodes[index]) {
                  nodes.swapAt(left, index)
                  index = left
              } else {
                  break
              }
          } else {
              break
          }
      }

      return result
  }
}

extension Heap where T: Comparable {
    init() {
        self.init(comparer: >)
    }
}

// Heap By 라이노님 https://gist.github.com/JCSooHwanCho/a3f070c2160bb8c0047a5ddbb831f78e

struct EdgeData : Comparable{
    static func < (lhs: EdgeData, rhs: EdgeData) -> Bool {
        lhs.cost < rhs.cost
    }
    
    var cost : Int
    var node : Int
}


func solution(){
    let inf = 7777777
    let firstLine = readLine()!.split(separator: " ").map({Int(String($0))!})
    let v = firstLine[0]
    let e = firstLine[1]
    
    let start = Int(readLine()!)! - 1
    
    var graph = Array(repeating: [(Int,Int)]() , count: v)
    for _ in 0..<e{
        let line = readLine()!.split(separator: " ").map({Int(String($0))!})
        graph[line[0]-1].append((line[1]-1,line[2]))
    }
    

    var d = Array(repeating: inf, count: v)
    d[start] = 0

        
    var pq: Heap = Heap<EdgeData>()
    pq.insert(EdgeData(cost: 0,node: start))
    while(!pq.isEmpty){
        let now = pq.delete()!
        if d[now.node] < now.cost{
            continue
        }
        
        for next in graph[now.node]{

            if now.cost + next.1 < d[next.0]{
                d[next.0] = now.cost + next.1
                pq.insert(EdgeData(cost: now.cost + next.1,node: next.0))
            }
        }
    }
    for i in d{
        if i == inf{
            print("INF")
        } else {
            print(i)
        }
    }
    
}

solution()