[백준/Swift] 14938: 서강그라운드 | PS일지

문제

14938번: 서강그라운드

간단한 문제 요약

  여러 지역 중 한 지역에 떨여졌을 때 각 지역에 아이템이 몇 개 있는지 알려주는 프로그램을 개발했다. 하지만 어디로 떨어져야 수색 범위 내에서 많은 아이템을 얻어야 할지는 모른다. 낙하한 지역을 중심으로 수색 범위가 주어진다고 할 때 수색 범위 이내에서 가장 많이 얻을 수 있는 아이템 개수를 구하시오.

 

고려해야 할 사항

• X

문제 풀이, 새로 알게된 것

 수색범위는 문제에서 주어집니다. 예은이가 떨어졌을 때의 지점을 시작 정점으로 다익스트라 탐색을 한 후에 수색 범위 이내에 해당하는 정점의 아이템의 합을 구하면 됩니다. 이때 예은이가 떨어지는 지점은 정해지지 않았음으로 플로이드 와샬 또는 모든 정점에서 각각의 정점들을 시작 정점으로 다익스트라 탐색을 진행한 후 아이템의 최대로 얻을 수 있는 개수를 출력하면 됩니다.

 

 저는 힙 구현에 익숙해져서 복습겸 다익스트라를 통해 모든 정점의 각 정점을 시작정점으로 하는 다익스트라 탐색을 진행해 일정 수색 범위 이내라면 아이템값들을 더해서 최대의 경우를 찾는 방식으로 구현했습니다.

 

Code

r nmr = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (nCnt,mRange,eCnt) = (nmr[0],nmr[1],nmr[2])
var items = readLine()!.split{$0==" "}.map{Int(String($0))!}
var graph = Array(repeating: [Node](), count: nCnt)
var res = 0
_=(0..<eCnt).map { _ in
    let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
    let (s,e,c) = (input[0]-1,input[1]-1,input[2])
    graph[s].append(Node(vertex: e, cost: c))
    graph[e].append(Node(vertex: s, cost: c))
}
for i in 0..<nCnt {
    var dir = Array(repeating: Int.max, count: nCnt)
    var temp = 0
    dijkstra(i, dir: &dir)
    _=dir.enumerated().filter{$0.element <= mRange}.map{temp += items[$0.offset]}
    res = max(res, temp)
}
print(res)

Dijkstra

func dijkstra(_ start: Int, dir: inout [Int]) {
    var priority = Heap<Node>()
    priority.insert(Node(vertex: start, cost: 0))
    dir[start] = 0
    while !priority.isEmpty {
        guard let pop = priority.delete() else {
            break
        }
        if pop.cost > dir[pop.vertex] {
            continue
        }
        for node in graph[pop.vertex] {
            if dir[node.vertex] > dir[pop.vertex] + node.cost {
                dir[node.vertex] = dir[pop.vertex] + node.cost
                priority.insert(Node(vertex: node.vertex, cost: dir[node.vertex]))
            }
        }
    }
}

Model (Heap, Node)

struct Heap<T> where T: Comparable {
    private var list = [T]()
    private var isLeftSmall: (T,T) -> Bool
    init(isLeftSmall: @escaping (T,T)-> Bool) {
        self.isLeftSmall = isLeftSmall
    }
    init() {
        self.init(isLeftSmall: <)
    }
}

extension Heap {
    var isEmpty: Bool {
        return list.isEmpty
    }
    var count: Int {
        return list.count
    }
}
extension Heap {
    mutating func insert(_ element: T) {
        var idx = list.count
        list.append(element)
        while idx > 0 && isLeftSmall(list[idx], list[(idx-1/2)]) {
            list.swapAt(idx, (idx-1)/2)
            idx = (idx-1)/2
        }
    }
    mutating func delete() -> T? {
        guard !isEmpty else {
            return nil
        }
        guard 1 != count else {
            return list.removeFirst()
        }
        var idx = 0
        let element = list.first!
        list.swapAt(idx, count-1)
        _=list.removeLast()
        while idx > 0 {
            let (left,right) = (idx*2+1,idx*2+2)
            if right < count {
                if isLeftSmall(list[left],list[right]) && isLeftSmall(list[left],list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else if isLeftSmall(list[right],list[idx]) {
                    list.swapAt(right, idx)
                    idx = right
                } else {
                    break
                }
            } else if left < count {
                if isLeftSmall(list[left],list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else {
                    break
                }
            } else {
                break
            }
        }
        return element
    }
}

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