백준 10473 - 인간 대포 - swift

https://www.acmicpc.net/problem/10473

10473번: 인간 대포

 

 

 

 

두 점사이의 거리공식만 안다면 풀수있다. 

물론 조금의 고민이 필요하다. 

 

우선 대포는 어떤 방향이든 50m로 날라갈수있다고 했다. 

즉 대포는 50m주변 원으로 날라갈 수 있는데 조금만 고민해보면 어느지점으로 날라가야할지 알 수 있다.

 

답은 대포지점과 다른점 사이의 직선으로 날라가면 된다. 

즉 두 점 사이의 직선의 방정식안에서 50m로 날라가면된다.

하지만 이렇게 50m가 되는 지점을 찾을수없다. 무수히 많은 점들이있기때문에 하나를 찾기란 쉽지않을 것이다. 

 

조금만 고민해보면, 두 점사이의 거리라는 것을 깨달을수 있다. 

즉 두점사이의 거리가 50m이상이라면? 예를 들어 대포와 어떤점의 사이의 거리가 70m면, 50m는 대포로날라가고, 나머지 20m는 걸어가면될 것이다. 

30m라면, 50m대포로날라가고 다시 20m되돌아오면 될것이다.

또한 대포로 날라가지않고 걸어가는 경우도 생각할수있다. 

즉 대포에서 출발할때는 걸어가거나 대포로날라가거나, 대포로날라가서 추가로 걷거나 에서 최소비용을 선택하면된다. 

 

이렇게 모든지점으로부터 비용들을 계산한다음 다익스트라를 이용하여 도착지점까지의 최소비용을 갱신해나가며 답을 찾으면된다. 

swift에서는 heap 자료구조를 지원하지않으므로 추가로 구현하면된다.

 

import Foundation

struct Heap<T: Comparable> {
    var list = [T]()
    var comparer: (T,T) -> Bool
    init(_ comparer: @escaping (T,T) -> Bool ) {
        self.comparer = comparer
    }
    
    mutating func insert(_ x: T) {
        var idx = list.count
        list.append(x)
        while idx>0, comparer(list[(idx-1)/2], list[idx]) {
            list.swapAt(idx, (idx-1)/2)
            idx = (idx-1)/2
        }
    }
    mutating func delete() -> T? {
        if list.isEmpty { return nil }
        list.swapAt(0, list.count-1)
        let deleted = list.removeLast()
        var idx = 0, change = -1
        
        while idx<list.count{
            for k in idx*2+1...idx*2+2 {
                if k<list.count, comparer(list[idx], list[k]) {
                    if change == -1 || comparer(list[change], list[k]) {
                        change = k
                    }
                }
            }
            if change == -1 { break }
            list.swapAt(idx, change)
            idx = change
            change = -1
        }
        return deleted
    }
    
    var isEmpty: Bool { return list.isEmpty}
}

let inp = readLine()!.split(separator: " ").map{Float(String($0))!}
let sx = inp[0], sy = inp[1]
let inp2 = readLine()!.split(separator: " ").map{Float(String($0))!}
let ex = inp2[0], ey = inp2[1]
let N = Int(readLine()!)!
var list = [(Float,Float)]()
list.append((sx,sy))
list.append((ex,ey))

for _ in 0..<N {
    let q = readLine()!.split(separator: " ").map{Float(String($0))!}
    let x = q[0], y = q[1]
    list.append((x,y))
}
var paths = Array(repeating:[(Int, Float)](), count: N+2)

for i in 0..<N+2 {
    for j in 0..<N+2 {
        if i == j { continue }
        let x = list[i].0-list[j].0
        let y = list[i].1-list[j].1
        let dist = sqrt(x*x+(y*y))
        var time: Float = dist/5
        if i < 2 {
            time = dist/5
            
        } else {
            if dist >= 50 {
                time = min(time, 2.0 + (dist-50)/5)
            } else {
                time = min(time, 2.0 + (50-dist)/5)
            }
        }
        paths[i].append((j,time))
    }
}

struct Node: Comparable {
    var idx: Int
    var time: Float
    static func < (lhs: Node, rhs: Node) -> Bool {
        return lhs.time < rhs.time
    }
}
var times: [Float] = Array(repeating: 99999999999.0, count: N+2)
times[0] = 0.0

var queue = Heap<Node>(>)
queue.insert(Node(idx: 0, time: 0.0))

while !queue.isEmpty {
    let f = queue.delete()!
    if times[f.idx] < f.time { continue }
    if f.idx == 1 {
        print(f.time)
        break
    }
    
    for next in paths[f.idx] {
        let time = f.time + next.1
        if times[next.0] > time {
            times[next.0] = time
            queue.insert(Node(idx: next.0, time: time))
        }
    }
}