[17396] 백도어

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

17396번: 백도어

최단거리 탐색 문제다. 다익스트라 알고리즘으로 접근했다.

---

풀이

접근 가능한 정점과 N-1번 정점을 이어주는 간선들만 저장했다.

 

swift에는 다른 언어들과 달리 Heap이 구현되어있지 않아서 일반적인 경우에는 일반 큐를 사용하여 매 순환마다 정렬 작업을 하여 탐색하였는데 이번 문제는 간선정보가 최대 300,000개가 주어지므로 Heap 구현이 필요했다.

글 읽기 - 다익스트라 시간초과 질문드립니다

그런데 마주한 시간초과. 질문게시판을 찾아보니 다익스트라 알고리즘의 원리를 잘 고민하면 우선순위 큐를 더 빠르게 탐색이 가능하다고 한다. 

 

우선 다익스트라 알고리즘은 비용이 낮은 순으로 정렬된 우선순위 큐를 탐색하여 매 순간 각 정점으로의 최소비용을 갱신하게 된다.

즉, [현재 정점의 최소비용 + 현재 정점에서 다음 정점까지의 비용] 계산을 통해 다음 정점의 최단거리 정보를 갱신하는데, 이때 우선순위 큐에서 꺼낸  현재 정점의 정보가 최소 비용이 아니라면 결국 다음 정점까지의 정보를 탐색할 필요가 없다는 얘기다.

 

따라서 매 탐색마다 최단거리 정보를 담고 있는 cost[curr]와 우선순위 큐에 담겨있는 curr.cost 와의 비교를 통해서 최단거리보다 큰 비용이라면 continue를 통해 시간단축이 가능하다.

---

정답 코드

	import Foundation
	//by rhyno
	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: <)
	}
	}
	let (N,M) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
	var node = readLine()!.split(separator: " ").map{$0=="0" ? true:false}
	var map = Array(repeating: [(node:Int, cost:Int)](), count: N)
	var visited = Array(repeating: false, count: N)
	var q = Heap<(node:Int, cost:Int)>(comparer: {$0.cost > $1.cost})
	var cost = Array(repeating: -1, count: N)
	for _ in 0..<M{
	let (u,v,cost) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1], $0[2])}[0]
	if (u==N-1 && node[v]) || (v==N-1 && node[u]) || (node[u] && node[v]){
	map[u].append((v,cost))
	map[v].append((u,cost))
	}
	}
	cost[0] = 0
	q.insert((0,0))
	while !q.isEmpty{
	let curr = q.delete()!
	if cost[curr.node] < curr.cost { continue }
	for next in map[curr.node]{
	let newCost = cost[curr.node] + next.cost
	if cost[next.node]<0 || cost[next.node]>newCost{
	cost[next.node] = newCost
	q.insert((next.node, newCost))
	}
	}
	}
	print(cost[N-1])

view raw 17396.swift hosted with ❤ by GitHub