백준 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를 출력하면 된다.

 

문제 링크

1753번: 최단경로

 

 

풀이

---

문제 이름부터 '최단경로' 인 이 문제는 최단 경로 알고리즘으로 유명한 '다익스트라 알고리즘' 을 이용하면 금방 풀 수 있다.

다익스트라 알고리즘 설명은 아래의 링크에 정리해두었다.▼

다익스트라

 

 

프로그램 동작

---

이 문제의 경우 무방향이 아니라 방향 그래프이므로, 다음에 갈 노드만 저장해놓으면 뒤로 돌아갈 일은 없게 된다.

그래서 5 1 1 과 같이 들어오게 되면,

가장 앞의 5번 노드의 칸으로 가서 다음에 갈 노드 정보를 1로, 그리고 그 길이는 1로 저장해준다.

그래서 일단은 (노드 정보, 길이) 쌍을 가진 튜플 2차원 배열을 선언해줬다.

2차원 배열인 이유는 한 노드에서 여러 노드로 이동할 수 있기 때문에 여러 개의 노드 정보가 한 노드로 들어오는 걸 받기 위해서 이다.▼

 

 

이렇게 노드 정보를 받고 나면, 앞에서 봤던 다익스트라 알고리즘을 이 노드들을 토대로 실행시켜주면 된다.

 

 

Swift 코드

---

import Foundation

// 라이노님의 FileIO
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45{ isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""var now = read()

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

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: >)
    }
}

struct Data : Comparable {
    static func < (lhs: Data, rhs: Data) -> Bool {
        lhs.cost < rhs.cost
    }

    var cost : Int
    var node : Int
}

var file = FileIO()
let V = file.readInt()
let E = file.readInt()
let S = file.readInt()
var info = Array(repeating: [(Int, Int)](), count: V + 1)
var distance = Array(repeating: Int.max, count: V + 1)

for _ in 0..<E {
    info[file.readInt()].append((file.readInt(), file.readInt()))
}

func dijkstra(_ start: Int) {
    distance[start] = 0

    var Q = Heap<Data>()
    Q.insert(Data(cost: 0, node: start))

    while !Q.isEmpty {
        let now = Q.delete()!
        if distance[now.node] < now.cost {
            continue
        }
        for next in info[now.node] {
            if now.cost + next.1 < distance[next.0] {
                distance[next.0] = now.cost + next.1
                Q.insert(Data(cost: now.cost + next.1, node: next.0))
            }
        }
    }
}

dijkstra(S)

var answer = ""for i in 1...V {
    if distance[i] == Int.max {
        answer.append("INF")
    } else {
        answer.append("\(distance[i])")
    }
    if i != V {
        answer.append("\n")
    }
}
print(answer)

 

Swift에는 자료구조가 정의 되어 있는 라이브러리가 없다.

그래서 자료구조들을 직접 구현해야 하는데, 힙은 정말 구현하기 까다롭다.

그리고 나는 내가 직접 만들어서 제출하니 너무 느리다고 시간초과를 받았다.

더 빠르게 만드는 방법을 몰라서 어쩔 수 없이 라이노님이 만든 힙 구조체를 사용했더니 시간초과는 면했다.

그래서 처음에는 약 700ms가 나왔는데, 여기에 라이노님이 만든 fileIO 클래스를 가져와 적용시키니 시간이 100m대로 대폭 줄었다...

기존의 readLine()함수는 거대한 하나의 데이터(길이가 10000인 String 1개)는 준수한 속도로 읽어오지만, 작은 여러 개의 데이터(길이가 1인 String 10000개)를 읽는데는 꽤 오래 걸린다.

그래서 가끔 조그마한 데이터를 수만번 입력받아야할 때면, 입력 받는 부분 때문에 시간초과가 나기도 한다.

이럴 때는 라이노님이 fileHandle을 이용해 만든 fileIO(빠른 입출력 클래스)를 사용하지 않으면, 알고리즘으로 시간을 대폭 줄여도 통과하지 못할 수도 있다.

그래서 무작정 fileIO를 사용하는건 코드 길이가 길어져서 추천하진 않지만, 작은 데이터를 수만 번 받는 상황이라면 fileIO를 사용하는걸 추천한다.

 

입력에서 부터 시간초과가 발생할 수 있는 Swift는 정말...