18352 swift - 특정 거리의 도시 찾기

2024. 10. 2. 07:42ㆍ🐣/BOJ

처음 접근 - 벨만 포드
벨만 포드 풀이 시간초과 코드 보기.

더보기

이유. O(V * E) 

벨만-포드 알고리즘의 시간 복잡도는 **O(V * E)**입니다. 여기서 V는 정점의 수, E는 간선의 수를 의미합니다.

주어진 문제에서:

  • N (정점의 수) = 최대 300,000
  • M (간선의 수) = 최대 1,000,000

따라서 벨만-포드를 사용했을 때 최악의 경우 시간 복잡도는:

O(V×E)=O(300,000×1,000,000)=300,000,000,000O(V \times E) = O(300,000 \times 1,000,000) = 300,000,000,000O(V×E)=O(300,000×1,000,000)=300,000,000,000

즉, 300조의 연산을 수행해야 합니다.

 

import Foundation

let INF = 987654321

struct Edge {
    var s: Int, e: Int, t: Int
}

let nmkx = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m, k, x) = (nmkx[0], nmkx[1], nmkx[2], nmkx[3])
var edges = [Edge]()

for _ in 0..<m {
    let se = readLine()!.split(separator: " ").map{Int(String($0))!}
    edges.append(Edge(s: se[0], e: se[1], t: 1))
}

var dist = Array(repeating: INF, count: n + 1)
dist[x] = 0

for _ in 0..<n-1 {
    for edge in edges {
        if dist[edge.e] > dist[edge.s] + edge.t {
            dist[edge.e] = dist[edge.s] + edge.t
        }
    }
}

var result = ""

for (i, v) in dist.enumerated() {
    if v == k {
        result += "\(i)\n"
    }
}

print(result == "" ? "-1" : result)

 

BFS 풀이 코드. 링크드리스트로 Queue를 구현하여 풀이.

시간 복잡도: O(V + E)

  • V: 그래프의 정점(Vertex) 개수
  • E: 그래프의 간선(Edge) 개수

BFS 시간 복잡도 분석

  1. 정점 방문:
    • 각 정점을 한 번만 방문합니다. BFS는 큐에 정점을 추가할 때 그 정점을 방문했다고 표시하므로, 각 정점은 최대 한 번만 큐에 들어가고 큐에서 꺼내집니다.
    • 따라서 정점을 방문하는 시간 복잡도는 O(V)입니다.
  2. 간선 탐색:
    • 각 정점에서 연결된 모든 간선을 확인합니다. 이 과정에서 간선을 따라 이동할 때, 그 간선은 최대 한 번만 사용됩니다.
    • 따라서 간선을 탐색하는 시간 복잡도는 O(E)입니다.

BFS의 총 시간 복잡도

  • BFS는 큐에 정점을 넣고, 큐에서 정점을 꺼내면서 그 정점에 연결된 모든 간선을 탐색합니다.
  • 모든 정점을 한 번 방문하고, 모든 간선을 한 번씩 확인하므로 시간 복잡도는 O(V + E)가 됩니다.

BFS 시간 복잡도의 의미

  • V와 E의 관계에 따라 그래프가 다르지만, 보통 E가 V에 비해 많을 수 있기 때문에 O(V + E)로 시간 복잡도를 표현합니다.
  • 희소 그래프 (Sparse Graph): 간선의 수가 정점의 수와 비슷한 경우 (즉, E ≈ V) - 시간 복잡도는 O(V)에 가까워집니다.
  • 밀집 그래프 (Dense Graph): 간선의 수가 정점의 수의 제곱에 가까운 경우 (즉, E ≈ V^2) - 시간 복잡도는 O(E)에 가까워집니다.

BFS와 시간 초과 문제

  • 주어진 문제에서 정점의 수 N ≤ 300,000, 간선의 수 M ≤ 1,000,000으로 가정하면:
    • 시간 복잡도는 O(V + E) = O(300,000 + 1,000,000) = O(1,300,000)입니다.
    • 이는 일반적인 알고리즘 문제에서 제한 시간인 1초에 충분히 처리할 수 있는 범위 내에 있습니다. 보통 1초에 약 10^8번의 연산이 가능하다고 가정하기 때문에 BFS는 이 크기의 입력에서도 효율적으로 실행될 수 있습니다.

BFS와 우선순위 큐 사용 시 차이점

  • BFS는 모든 간선의 가중치가 같을 때 최적의 시간 복잡도를 가지며 간단하게 구현할 수 있습니다.
  • 다익스트라 알고리즘은 가중치가 다를 때 최소 비용 경로를 탐색하기 위해 우선순위 큐를 사용합니다. 이때 우선순위 큐의 삽입과 삭제에 O(log V)가 소요되기 때문에 BFS보다 다소 복잡하지만, 가중치가 다를 때 더 효율적으로 사용할 수 있습니다.

Swift 링크드리스트로 구현한 큐(Queue)

더보기
class LinkedListNode<T> {
    let value: T
    weak var previous: LinkedListNode?
    var next: LinkedListNode?
    
    init(value: T) {
        self.value = value
    }
}

struct LinkedList<T> {
    
    var isEmpty: Bool {
        return self.head == nil
    }
    
    mutating func appendValue(_ value: T) {
        let new = LinkedListNode<T>(value: value)
        
        if self.isEmpty {
            self.head = new
        } else {
            self.tail?.next = new
            new.previous = self.tail
        }
        
        self.tail = new
    }
    
    mutating func removeHead() -> T? {
        guard let head = self.head else { return nil }
        return self.removeNode(head)
    }
    
    mutating func removeTail() -> T? {
        guard let tail = self.tail else { return nil }
        return self.removeNode(tail)
    }
    
    mutating func removeNode(_ node: LinkedListNode<T>) -> T {
        if let prev = node.previous {
            prev.next = node.next
        } else {
            self.head = node.next
        }
        
        if let next = node.next {
            next.previous = node.previous
        } else {
            self.tail = node.previous
        }
        
        node.previous = nil
        node.next = nil
        
        return node.value
    }
    
    private(set) var head: LinkedListNode<T>?
    private var tail: LinkedListNode<T>?
}

struct QueueWithLinkedList<T> {
    
    var isEmpty: Bool {
        return self.linkedList.isEmpty
    }
    
    var front: T? {
        return self.linkedList.head?.value
    }
    
    mutating func enqueue(_ item: T) {
        self.linkedList.appendValue(item)
    }
    
    mutating func dequeue() -> T? {
        guard !self.isEmpty else { return nil }
        return self.linkedList.removeHead()
    }
    
    mutating func popLast() -> T? {
        guard !self.isEmpty else { return nil }
        return self.linkedList.removeTail()
    }
    
    private var linkedList = LinkedList<T>()
}
import Foundation

let nmkx = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m, k, x) = (nmkx[0], nmkx[1], nmkx[2], nmkx[3])

var graph = [[Int]](repeating: [], count: n + 1)

for _ in 0..<m {
    let ab = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[ab[0]].append(ab[1])
}

var distance = Array(repeating: -1, count: n + 1)
distance[x] = 0

var queue = QueueWithLinkedList<Int>()
queue.enqueue(x)

while !queue.isEmpty {
    guard let current = queue.dequeue() else {
        continue
    }

    for next in graph[current] {
        if distance[next] == -1 {
            distance[next] = distance[current] + 1
            queue.enqueue(next)
        }
    }
}

var result = [Int]()
for i in 1...n {
    if distance[i] == k {
        result.append(i)
    }
}

if result.isEmpty {
    print("-1")
} else {
    result.sort()
    for city in result {
        print(city)
    }
}

 

다익스트라 알고리즘의 특징

  • 시간 복잡도: O((V + E) * log V).
    • V는 정점의 개수 (n), E는 간선의 개수 (m)입니다.
    • 우선순위 큐에서 가장 작은 값을 꺼내고 삽입하는 데 소요되는 시간 복잡도는 log V이기 때문에, 그래프의 크기가 크더라도 효율적으로 처리할 수 있습니다.

Swift에서 우선순위큐를 활용한 다익스트라 알고리즘 코드
Swift에서 힙으로 구현한 우선순위 큐

더보기 
struct Heap<T> {
    var elements: [T] = []
    let priorityFunction: (T, T) -> Bool

    init(priorityFunction: @escaping (T, T) -> Bool) {
        self.priorityFunction = priorityFunction
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    func peek() -> T? {
        return elements.first
    }

    mutating func insert(_ value: T) {
        elements.append(value)
        siftUp(elementAtIndex: elements.count - 1)
    }

    mutating func remove() -> T? {
        guard !elements.isEmpty else {
            return nil
        }
        if elements.count == 1 {
            return elements.removeFirst()
        } else {
            let value = elements.first
            elements[0] = elements.removeLast()
            siftDown(elementAtIndex: 0)
            return value
        }
    }

    private mutating func siftUp(elementAtIndex index: Int) {
        let parent = parentIndex(of: index)
        guard !isRoot(index), priorityFunction(elements[index], elements[parent]) else {
            return
        }
        elements.swapAt(index, parent)
        siftUp(elementAtIndex: parent)
    }

    private mutating func siftDown(elementAtIndex index: Int) {
        let childIndex = highestPriorityIndex(for: index)
        if index == childIndex {
            return
        }
        elements.swapAt(index, childIndex)
        siftDown(elementAtIndex: childIndex)
    }

    private func isRoot(_ index: Int) -> Bool {
        return index == 0
    }

    private func leftChildIndex(of index: Int) -> Int {
        return 2 * index + 1
    }

    private func rightChildIndex(of index: Int) -> Int {
        return 2 * index + 2
    }

    private func parentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }

    private func highestPriorityIndex(for parent: Int) -> Int {
        let leftChild = leftChildIndex(of: parent)
        let rightChild = rightChildIndex(of: parent)

        var highest = parent
        if leftChild < elements.count && priorityFunction(elements[leftChild], elements[highest]) {
            highest = leftChild
        }
        if rightChild < elements.count && priorityFunction(elements[rightChild], elements[highest]) {
            highest = rightChild
        }
        return highest
    }
}
import Foundation

let nmkx = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m, k, x) = (nmkx[0], nmkx[1], nmkx[2], nmkx[3])

var graph = [[(node: Int, cost: Int)]](repeating: [], count: n + 1)

for _ in 0..<m {
    let ab = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[ab[0]].append((node: ab[1], cost: 1))
}

var distance = Array(repeating: Int.max, count: n + 1)
distance[x] = 0

var priorityQueue = Heap<(node: Int, cost: Int)> { (lhs: (node: Int, cost: Int), rhs: (node: Int, cost: Int)) in
    lhs.cost < rhs.cost
}
priorityQueue.insert((node: x, cost: 0))

while !priorityQueue.isEmpty {
    guard let current = priorityQueue.remove() else { break }
    let currentNode = current.node
    let currentCost = current.cost

    if currentCost > distance[currentNode] {
        continue
    }

    for neighbor in graph[currentNode] {
        let nextNode = neighbor.node
        let newCost = currentCost + neighbor.cost

        if newCost < distance[nextNode] {
            distance[nextNode] = newCost
            priorityQueue.insert((node: nextNode, cost: newCost))
        }
    }
}

var result = [Int]()
for i in 1...n {
    if distance[i] == k {
        result.append(i)
    }
}

if result.isEmpty {
    print("-1")
} else {
    result.sort()
    for city in result {
        print(city)
    }
}
저작자표시 비영리 변경금지

'🐣 > BOJ' 카테고리의 다른 글

1299 c++ - 전쟁-탈출편2  (0) 2024.10.05
1446 swift / c++ - 지름길  (0) 2024.10.04
12100 swift / c++ - 2048 (Easy)  (0) 2024.09.23
6603 swift - 로또  (0) 2024.04.28
1946 swift - 신입 사원 / 시간 초과 해결  (0) 2024.03.10

카테고리의 글 더보기

댓글 0

티스토리툴바