์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- arkit
- ๋ฐฑ์ค
- realm
- Lv2
- tableView
- rxcocoa
- ํ๋ก๊ทธ๋๋จธ์ค
- TCA
- ํจ์คํธ์บ ํผ์ค
- raywenderlich
- Kuring
- SwiftUI
- BOJ
- RxSwift
- Xcode
- Swfit
- SnapKit
- BFS
- Flutter
- node.js
- reactorkit
- ios
- designpattern
- combine
- XCTest
- visionOS
- MVVM
- swift
- UIKit
- CollectionView
Archives
- Today
- Total
lgvv98
[Swift] BOJ 1753 ์ต๋จ๊ฒฝ๋ก ๋ณธ๋ฌธ
BOJ 1753 ์ต๋จ๊ฒฝ๋ก
โ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ฅ ๋ํ์ ์ธ ๋ฌธ์ ์์.
๊ทผ๋ฐ ๋ ๋ชปํ ..ใ
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๋ง์๋๋ฐ ์๊พธ ์๊ฐ์ด๊ณผ๊ฐ ๋๋๊ฑฐ์.
๊ทผ๋ฐ ๋์ค์ ์๊ณ ๋ณด๋๊น ์๋ฃ๊ตฌ์กฐ ํ์ ์ฌ์ฉํ์ง ์์์๋๋ฌ๊ตฐ !_!
๊ทธ๋์ ๋ค๋ฅธ ์ฌ๋ ์๊ณ ๋ฆฌ์ฆ ๊ธฐ๋ฐ์ผ๋ก ํ์ตํ๊ธฐ๋ก ํจ. ์ฌ๊ธฐ์ ์๊ฐ ๋๋ฌด ์ก์๋จน๊ธธ๋,, ์๋๋ฉด ํ๋ถํฐ ํ๊ณ ๋ค์ ๋์์์ผ์ง.
โ ๋ด ์ฝ๋ - ์๊ฐ์ด๊ณผ
struct b1753 {
static func run() {
// ์
๋ ฅ๋ถ
let firstLine = readLine()!.split(separator: " ").map( {Int(String($0))! })
let secondLine = Int(readLine()!)!
var table = [Int](repeating: Int(1e9), count: firstLine[0]+1)
var graph = [Int: [Int: Int]]()
for i in 1...firstLine[0] {
graph[i] = [:]
}
for _ in 0..<firstLine[1] {
let info = readLine()!.split(separator: " ").map { Int($0)! }
let start = info[0]
let end = info[1]
let weight = info[2]
var temp = graph[start]!
if temp[end] == nil {
temp[end] = weight
} else {
temp[end] = min(temp[end]!, weight)
}
graph[start] = temp
}
// ๊ตฌํ๋ถ - ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํฉ๋๋ค.
var priorityQueue = [(Int, Int)]()
var visited = [secondLine] // ๋ฐฉ๋ฌธํ ๋
ธ๋
table[secondLine] = 0
graph[secondLine]!.forEach {
priorityQueue.append(($0.key,$0.value))
}
priorityQueue = priorityQueue.sorted { $0.1 > $1.1 }
var popNode = secondLine
while !priorityQueue.isEmpty {
// ํ
์ด๋ธ ์
๋ฐ์ดํธ
priorityQueue.forEach { (node, weight) in
if !visited.contains(node) {
table[node] = min(table[node], weight + table[popNode])
}
}
// ์ฐ์ ์์ ํ ์
๋ฐ์ดํธ -> ๋ค์ ์์
์ ์ํจ.
popNode = priorityQueue.last!.0
visited.append(popNode)
priorityQueue.removeAll()
graph[popNode]?.forEach{
priorityQueue.append(($0.key,$0.value))
}
priorityQueue = priorityQueue.sorted { $0.1 > $1.1 }
}
// ์ถ๋ ฅ๋ถ
table[1...].forEach {
if $0 == Int(1e9) {
print("INF")
} else {
print($0)
}
}
}
}
โ ์ ๋ต์ฝ๋ - ์ถ์ฒ๋ ์ ์ผ ์๋์ ์์ต๋๋ค.
import Foundation
struct PriorityQueue<T> {
var array = [T]()
let sort: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.sort = sort
}
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
func peek() -> T? {
return array.first
}
func leftChildIndex(ofParentAt index: Int) -> Int {
return (2 * index) + 1
}
func rightChildIndex(ofParentAt index: Int) -> Int {
return (2 * index) + 2
}
func parentIndex(ofChildAt index: Int) -> Int {
return (index - 1) / 2
}
// MARK:- remove operation
mutating func pop() -> T? {
guard !isEmpty else {
return nil
}
array.swapAt(0, count - 1)
defer {
siftDown(from: 0)
}
return array.removeLast()
}
mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = leftChildIndex(ofParentAt: parent)
let right = rightChildIndex(ofParentAt: parent)
var candidate = parent
if left < count && sort(array[left], array[candidate]) {
candidate = left
}
if right < count && sort(array[right], array[candidate]) {
candidate = right
}
if candidate == parent {
return
}
array.swapAt(parent, candidate)
parent = candidate
}
}
// MARK:- insert operation
mutating func push(_ element: T) {
array.append(element)
siftUp(from: array.count - 1)
}
mutating func siftUp(from index: Int) {
var child = index
var parent = parentIndex(ofChildAt: child)
while child > 0 && sort(array[child], array[parent]) {
array.swapAt(child, parent)
child = parent
parent = parentIndex(ofChildAt: child)
}
}
}
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = Int(readLine()!)!
let v = input[0], e = input[1]
let INF = Int(1e9)
var edges = [[(Int, Int)]](repeating: [(Int, Int)](), count: v + 1)
for _ in 0..<e {
let i = readLine()!.split(separator: " ").map { Int(String($0))! }
edges[i[0]].append((i[1], i[2]))
}
var dist = [Int](repeating: INF, count: v + 1)
var pq = PriorityQueue<(Int, Int)>(sort: { $0.1 < $1.1 })
dist[k] = 0
pq.push((k, 0))
while !pq.isEmpty {
let (now, cost) = pq.pop()!
if cost > dist[now] {
continue
}
for (next, w) in edges[now] {
if dist[now] + w <= dist[next] {
dist[next] = dist[now] + w
pq.push((next, dist[next]))
}
}
}
for i in 1...v {
if dist[i] < INF {
print(dist[i])
} else {
print("INF")
}
}
(์ถ์ฒ)
https://github.com/skyqnaqna/algorithm_study/blob/main/boj/Dijkstra/BOJ_1753.swift#L8
'์ฝ๋ฉํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Swift] ํ๋ก๊ทธ๋๋จธ์ค LV2. ํฐ ์ ๋ง๋ค๊ธฐ (4) | 2022.04.13 |
---|---|
[Swift] ํ๋ก๊ทธ๋๋จธ์ค LV2. ์ฟผ๋ ์์ถ ํ ๊ฐ์ ์ธ๊ธฐ (0) | 2022.04.13 |
[Swift] ํ๋ก๊ทธ๋๋จธ์ค LV2. ์ ๋ ฅ๋ง์ ๋๋ก ๋๋๊ธฐ (0) | 2022.04.06 |
[Swift] BOJ 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์ (0) | 2022.04.05 |
[Swift] BOJ 1697 ์จ๋ฐ๊ผญ์ง (2์ฐจ์ ๋ฐฐ์ด๋ณด๋ค 1์ฐจ์ ํํ ๋ฐฐ์ด) (0) | 2022.04.05 |
Comments