Dijkstra

문제 https://www.acmicpc.net/problem/6087 풀이 다익스트라 알고리즘을 사용하여 해결하는 문제이다. 각 인접한 노드가 연결되어있다고 생각하고, 전의 노드에서 현재 노드로 온 방향과 수직인 노드만 거리를 1로 설정해주면 된다. 일반적인 다익스트라 알고리즘 문제에서는 연결된 노드간의 거리가 주어지는데, 이 문제에서는 연결된 노드의 거리를 0으로 할지, 1로 할지 선택해야한다. 하지만 다익스트라 알고리즘과 BFS의 관계를 잘 생각해보면, 어렵지 않게 풀 수 있다(개인적으로 BFS는 일종의 다익스트라 특이 케이스라고 생각한다.) 알고리즘은 다음과 같다. 그래프에서 인접한 칸끼리는 서로 연결된 노드라고 가정함 (노드간 거리는 기본적으로 0으로 생각) 현재 있는 칸에서 내가 바라보고 있는 방향을 기준으로 수직인 노드는 거리가 1, 아닌 노드는 0으로 설정 2.를 반복하면서 다익스트라 수행 vertical은 가로 이동 horizontal은 세로 이동 neutral은 중립 방향인데, 시작 지점이나 아래에서 설명할 다른 Direction이지만 같은 거리에 있는 노드가 가지는 방향이다. none은 아직 탐색하지 않은 노드가 가지는 방향이다. ...

문제 https://www.acmicpc.net/problem/1753 풀이 다익스트라 입문 문제이다. 단, 스위프트로 풀려면 힙을 직접 구현해야 한다. 입력으로 주어지는 엣지의 웨이트가 모두 같다는 조건이 없으므로, BFS가 아닌 다익스트라로 탐색해야 한다. 코드 import Foundation struct Heap { var heap: [(Int, Int)] = [] func isEmpty() -> Bool { return heap.isEmpty ? true : false } mutating func insert(_ value: (Int, Int)) { heap.append(value) var currentIndex = heap.count - 1 while currentIndex > 0 { let parentIndex = (currentIndex - 1) / 2 if heap[currentIndex].1 < heap[parentIndex].1 { heap.swapAt(currentIndex, parentIndex) currentIndex = parentIndex } else { break } } } mutating func deleteMin() -> (Int, Int) { if heap.isEmpty{ return (0, 0) } let min = heap[0] heap[0] = heap[heap.count - 1] heap.removeLast() var currentIndex = 0 while true { let leftChildIndex = 2 * currentIndex + 1 let rightChildIndex = 2 * currentIndex + 2 if leftChildIndex >= heap.count { break } var minChildIndex = leftChildIndex if rightChildIndex < heap.count && heap[rightChildIndex].1 < heap[leftChildIndex].1 { minChildIndex = rightChildIndex } if heap[minChildIndex].1 < heap[currentIndex].1 { heap.swapAt(currentIndex, minChildIndex) currentIndex = minChildIndex } else { break } } return min } } func dijkstra(k: Int) { var heap = Heap() heap.insert((k, 0)) distanceTable[k] = 0 while !heap.isEmpty() { let edge = heap.deleteMin() if distanceTable[edge.0] < edge.1 { continue } for node in graph[edge.0] { let cost = edge.1 + node.1 if cost < distanceTable[node.0] { distanceTable[node.0] = cost heap.insert((node.0, cost)) } } } } let ve = readLine()!.split(separator: " ").map { Int(String($0))! } let k = Int(readLine()!)! var graph = [[(Int, Int)]](repeating: [], count: ve[0] + 1) for _ in 0..<ve[1] { let uvw = readLine()!.split(separator: " ").map { Int(String($0))! } graph[uvw[0]].append((uvw[1], uvw[2])) } var distanceTable = [Int](repeating: 300_001, count: ve[0] + 1) dijkstra(k: k) for i in 1...ve[0] { if distanceTable[i] == 300_001 { print("INF") } else { print(distanceTable[i]) } }