[프로그래머스] Swift - 등산코스 정하기

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

2023.09.02 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

1. Gate에서 출발하여 Summit까지 갔다가 다시 Gate로 돌아오는 동선들을 구한다.
2. 동선 중에서 intsensity가 최소일 때를 리턴한다.
3. intensity는 경로를 구성하는 각 간선들의 가중치 중 최댓값을 의미한다.
4. 경로에서 출발지와 도착지 Gate는 같아야 하며 도중에 다른 Gate를 방문하면 안된다.
5. Summit은 단 1번만 방문해야 한다.

 

문제 조건을 요약하면 위와 같습니다.

 

우선 첫번째 문제 조건에서 첫번째 조건을 잘 생각해보면 봉우리까지 갔다가 다시 돌아오는걸 전부 구해야 하는 것처럼 말하지만 사실 그럴 필요가 없습니다.

출발지는 도착지와 같아야 한다는 조건이 있기 때문에 출발지 ➡️ 봉우리로 한번 갔다면 돌아오는 길은 왔던 그대로 오면 됩니다.

이 과정에서 경로의 intensity는 변하지 않습니다.

 

따라서, 왕복 경로를 구할 필요 없이 출발지 Gate 부터 봉우리들까지의 Intensity들만 구하면 됩니다.

 

경로 문제에서는 역시 BFS와 다이크스트라 알고리즘이 효과적이기 때문에 그쪽으로 방향을 잡았습ㄴ디ㅏ.

 

4번 조건을 어떻게 만족시킬지 고민을 하다가 질문하기 탭에서 힌트를 얻었습니다. 

노드들을 탐색하다가 Gate 노드에 도착하고 다시 여기서 다른 노드들로 경로를 연결하면 4번 조건을 만족시키지 못합니다.

반대로 Summit 노드에 도착했다가 다시 해당 노드에서 다른 노드들로 경로를 연결해도 4번 조건을 만족시키지 못합니다.

 

이 문제를 해결하는 방법은 아주 간단했습니다.

 

Gate 또는 Summit 노드를 포함한 간선을 저장할 때는 단방향으로 경로 저장하는 것입니다.

 

문제에서 제공하는 paths 배열을 바탕으로 다들 2차원 배열이나 딕셔너리로 그래프를 구성할 것입니다.

예를 들어, [1, 2, 3] 을 받으면

graph[1][2] = 3

graph[2][1] = 3

이렇게 누 노드를 양방향으로 연결합니다. (일반적인 그래프 구성)

 

이 부분을 조금 수정하면 4번 조건을 쉽게 만족시킬 수 있습니다.

만약 연결하려는 노드 A가 Gate라면 

graph[A][B] = Cost 는 수행하지만 graph[B][A] = Cost 는 수행하지 않는 것입니다.

즉, 그래프의 출발지(Gate) 노드에서는 다른 노드로는 보낼 수 있지만 다른 노드에서 Gate 노드로 도착하는 것을 막기 위해 애초에 연결을 끊어 놓는 것입니다.

 

반대로 봉우리의 경우에는 도착 방향으로의 연결을 끊으면 됩니다.

노드 A가 Summit이라면

graph[B][A] = Cost 는 수행하고, graph[A][B] = Cost는 수행하지 않습니다.

이렇게 하면 한번 봉우리에 도착하면 다른 곳으로 이동하지 않고 경로 탐색이 멈추게 되므로 한 경로에서 여러 봉우리를 포함하는 것이 원천 차단됩니다.

 

Dijkstra

시간 복잡도를 낮추고 경로 탐색을 하기 위해 Dijstra를 사용했습니다.

MinHeap 기반의 PriorityQueue를 활용하여 Cost(intensity)가 최소일 경우들을 dequeue하여 특정 노드까지의 최소 비용(여기서는 최소 Intensity)를 구했습니다.

 

원래의 Dikstra에서는 최소 비용의 인접 노드에서 다음 노드까지의 최소 비용을 더하여 PriorityQueue에 저장하는 방식이지만 이번 문제에서는 전체 경로의 비용에는 관심이 없고 Intensity, 즉, 경로를 구선하는 간선 중에서 가장 비용이 큰 1개의 간선의 값만 저장하면 되기 때문에 연산 로직은 조금 수정했습니다. (아래의 코드 참고해주세요!)

 

처음 풀이에서는 각 gate마다 dijkstra를 수행해서 해당 gate에서 다른 노드들까지의 최소 Intensity를 구했는데 이렇게 하면 gate의 수가 최대 50,000 이기 때문에 dijkstra를 50,000번 수행하여 시간 초과가 발생했습니다. 

dikstrat 자체는 O(N*logN)이지만 이렇게 풀면 전체 시간 복잡도는 O(N^2 * logN)이 된 것입니다.

 

하지만 이문제에서는 gate마다 dijkstra를 수행할 필요가 없었습니다.

한번에 dijkstra를 수행할 때 처음부터 priority queue에 모든 gate들을 전부 넣고 시작하면 되는 문제였습니다.

 

이유

이 문제의 결과 값은 조건을 모두 만족하는 경로에서의 [봉우리, Intensity] 형태의 배열을 리턴하는 것입니다.

따라서 어디서 출발했는지는 전혀 필요가 없습니다.

우리는 어디에서 출발했는지 상관없이 출발지들 중 어디선가부터 봉우리까지의 최소 Intensity를 구하면 되는 것입니다.

 

따라서 처음 Priority Queue를 생성하고 Gate 노드들을 전부 넣고 한번만 다이크스트라를 실행하면 임의의 노드 X 까지의 최소 Intensity 값을 구할 수 있게 됩니다.

 

 

 

풀이

1. PriorityQueue 구현

public struct PriorityQueue<T: Comparable> {
    
    // MARK: - Properties
    
    private var heap: Heap<T>
    private let sortFunction: (T, T) -> Bool
    
    /// O(1)
    public var isEmpty: Bool {
        self.heap.isEmpty
    }
    
    /// O(1)
    public var count: Int {
        self.heap.count
    }
    
    /// O(1)
    public var peek: T? {
        self.heap.peek
    }
    
    // MARK: - initialization
    
    public init(sortFunction: @escaping (T, T) -> Bool) {
        self.sortFunction = sortFunction
        self.heap = Heap<T>(sortFunction: sortFunction)
    }
    
    // MARK: - Methods
    
    /// O(logN)
    public mutating func enqueue(_ item: T) {
        heap.insert(item)
    }
    
    /// O(logN)
    @discardableResult
    public mutating func dequeue() -> T? {
        return heap.remove()
    }
}

public struct Heap<T: Comparable> {
    
    // MARK: - Properties
    
    private var elements = [T]()
    private let sortFunction: (T, T) -> Bool
    
    /// O(1)
    public var isEmpty: Bool {
        self.elements.isEmpty
    }
    
    /// O(1)
    public var count: Int {
        return elements.count
    }
    
    /// O(1)
    public var peek: T? {
        elements.first
    }
    
    // MARK: - initialization
    
    public init(sortFunction: @escaping (T, T) -> Bool) {
        self.sortFunction = sortFunction
    }
    
    // MARK: - Methods
    
    private func parentIndex(of i: Int) -> Int {
        return (i - 1) / 2
    }
    
    private func leftChildIndex(of i: Int) -> Int {
        return 2*i + 1
    }
    
    private func rightChildIndex(of i: Int) -> Int {
        return 2*i + 2
    }
    
    /// O(N)
    public func contains(_ item: T) -> Bool {
        return elements.contains(where: { $0 == item })
    }
    
    /// O(logN)
    mutating
    public func insert(_ item: T) {
        elements.append(item)
        swimUp(elements.count - 1)
    }
    
    /// O(logN)
    mutating
    private func swimUp(_ index: Int) {
        var childIndex = index
        let child = elements[childIndex]
        var parentIndex = self.parentIndex(of: childIndex)
        
        while childIndex > 0 && sortFunction(child, elements[parentIndex]) {
            elements[childIndex] = elements[parentIndex]
            childIndex = parentIndex
            parentIndex = self.parentIndex(of: childIndex)
        }
        
        elements[childIndex] = child
    }
    
    /// root 노드를 제거
    /// O(logN)
    @discardableResult
    public mutating func remove() -> T? {
        guard !elements.isEmpty else { return nil }
        
        if elements.count == 1 {
            return elements.removeLast()
        } else {
            let value = elements[0]
            elements[0] = elements.removeLast()
            diveDown(0)
            return value
        }
    }
    
    /// 특정 인덱스의 노드 제거
    /// O(logN)
    @discardableResult
    public mutating func remove(at index: Int) -> T? {
        guard index < elements.count else { return nil }
        let lastIndex = elements.count - 1
        elements.swapAt(index, lastIndex)
        diveDown(from: index, until: lastIndex)
        swimUp(index)
        return elements.removeLast()
    }
    
    /// O(1)
    public mutating func removeAll() {
        self.elements = []
    }
    
    /// O(logN)
    private mutating func diveDown(_ index: Int) {
        diveDown(from: index, until: elements.count)
    }
    
    /// O(logN)
    private mutating func diveDown(from index: Int, until endIndex: Int) {
        let leftChildIndex = self.leftChildIndex(of: index)
        let rightChildIndex = self.rightChildIndex(of: index)
        
        var temp = index
        
        if leftChildIndex < endIndex && sortFunction(elements[leftChildIndex], elements[temp]) {
            temp = leftChildIndex
        }
        
        if rightChildIndex < endIndex && sortFunction(elements[rightChildIndex], elements[temp]) {
            temp = rightChildIndex
        }
        
        if temp == index { return }
        
        elements.swapAt(index, temp)
        diveDown(from: temp, until: endIndex)
    }
}

Priority Queue와 이를 위한 Heap 구현입니다.

Swift는 아쉽게도 이러한 자료구조를 기본 제공하지 않기 때문에 직접 구현해야 합니다..ㅠㅠ

저는 이전에 구현해둔 것들을 복붙하여 사용했습니다.

 

2. Node 구현

fileprivate struct Node: Comparable {
    let name: Int
    let cost: Int
    
    static func < (lhs: Node, rhs: Node) -> Bool {
        lhs.cost < rhs.cost
    }
}

PriorityQueue에 넣을 간단한 노드 타입입니다.

 

3. Graph 구현

fileprivate struct Graph {
    var data: [Int: [Int: Int]] = [:] // key: 노드, value: [key 노드와 연결된 노드: 가중치(비용)]
    let gates: Set<Int>
    let summits: Set<Int>
    
    init(gates: Set<Int>, summits: Set<Int>) {
        self.gates = gates
        self.summits = summits
    }
    
    mutating func insert(node1: Int, node2: Int, cost: Int) {
        // 게이트 검사
        if gates.contains(node1) {
            insertGate(gate: node1, node: node2, cost: cost)
        } else if gates.contains(node2) {
            insertGate(gate: node2, node: node1, cost: cost)
        }
        // 봉우리 검사
        else if summits.contains(node1) {
            insertSummit(summit: node1, node: node2, cost: cost)
        } else if summits.contains(node2) {
            insertSummit(summit: node2, node: node1, cost: cost)
        }
        // 둘 다 일반 노드
        else {
            insertBothway(node1: node1, node2: node2, cost: cost)
        }
    }
    
    mutating private func insertBothway(node1: Int, node2: Int, cost: Int) {
        self.data[node1, default: [:]].updateValue(cost, forKey: node2)
        self.data[node2, default: [:]].updateValue(cost, forKey: node1)
    }
    
    mutating private func insertGate(gate: Int, node: Int, cost: Int) {
        self.data[gate, default: [:]].updateValue(cost, forKey: node)
    }
    
    mutating private func insertSummit(summit: Int, node: Int, cost: Int) {
        self.data[node, default: [:]].updateValue(cost, forKey: summit)
    }
    
    func getAdjacentNodes(node: Int) -> [Int: Int] {
        return data[node, default: [:]]
    }
}

Graph를 저장할 때 2차원 배열을 사용해도 되지만 저는 딕셔너리를 선호합니다.

2차원 배열에서는 연결되지 않는 노드들간의 가중치도 저장하기 때문에 비효율이 발생하기 때문입니다.

 

이번 문제에서는 Gate, Summit에 해당하는 노드를 저장할 때는 양방향이 아닌 단방향으로 간선을 저장해야 하기 때문에 insert 로직이 복잡해졌습니다.

 

 

4. solution 함수 구현 (dijkstra)

fileprivate func solution(_ n:Int, _ paths:[[Int]], _ gates:[Int], _ summits:[Int]) -> [Int] {
    var graph = Graph(gates: Set(gates), summits: Set(summits))
    
    for path in paths {
        graph.insert(node1: path[0], node2: path[1], cost: path[2])
    }

    func dijkstra() -> [Int] {
        var intensity = Array(repeating: 10_000_000, count: n+1)

        var pq = PriorityQueue<Node> {
            $0.cost < $1.cost
        }
        
        for gate in gates {
            intensity[gate] = 0
            pq.enqueue(Node(name: gate, cost: 0))
        }

        while !pq.isEmpty {
            let cur = pq.dequeue()!
            let curCost = cur.cost
            
            if intensity[cur.name] < curCost {
                continue
            }
            
            let adjacents = graph.getAdjacentNodes(node: cur.name)
            
            for (next, cost) in adjacents {
                let nextCost = max(curCost, cost)
                
                if intensity[next] > nextCost {
                    intensity[next] = nextCost
                    pq.enqueue(Node(name: next, cost: nextCost))
                }
            }
        }
        
        return intensity
    }
    
    var result = [n, 10_000_000]
    
    let maxIntensity = dijkstra()
    
    let summits = summits.sorted()
    
    for summit in summits {
        if maxIntensity[summit] < result[1] {
            result[0] = summit
            result[1] = maxIntensity[summit]
        }
    }
    
    return result
}

먼저 그래프를 생성하고 간선 데이터를 저장합니다.

 

dijkstra 함수를 수행하고 얻은 Intensity 배열에서 봉우리 노드에 해당하는 값 중에서 최솟값을 리턴합니다.

이 때 summits을 오름차순으로 정렬하고 구해야 합니다. (문제 조건 중에 intensity가 같은 경우 봉우리 숫자가 작은 것을 리턴하라고 했기 때문)

 

dijstra 함수를 살펴보면

먼저 임의의 노드 X까지의 최소 Intensity를 저장하는 Intensity 배열을 생성합니다.

intensity[X]는 어떠한 Gate로부터 X까지의 최소 Intensity를 의미합니다.

 

PriorityQueue를 생성하고 최소 힙으로 설정합니다.

 

모든 gate들에 대응하는 노드를 생성하고 PQ에 전부 넣습니다.

 

BFS의 특성을 이용하여 반복문을 돌며 pq에서 dequeue를 합니다. (cur에 이 노드 저장)

cur.cost는 cur까지의 경로에서의 Intensity를 의미합니다.

만약 cur.cost가 intensity[cur.name] 보다 크다는 것이 현재 탐색중인 경로가 최소 비용(최소 Intensity)이 아니라는 것이기 때문에 continue로 스킵합니다. 

 

cur의 인접한 노드들을 그래프로부터 가져옵니다.

next 노드까지의 Intensity를 갱신하고 (max 사용)

PQ에 next 노드를 넣습니다.

 

이 과정을 반복하게 됩니다.

 

 

 

 

마무리

Dijkstra에 대한 이해가 필요했고 일반적인 Dijkstra에서는 전체 경로의 비용을 PQ에 넣지만 이번 문제에서는 Intensity를 PQ에 넣어야 했습니다.

 

Graph를 저장할 때 Gate, Summit 노드는 단방향으로만 간선을 저장해야 하는 아이디어도 필요했습니다. 

 

Swift에서는 PQ, Heap을 지원하지 않기 때문에 직접 구현해야 해서 코드 길이도 많이 증가했습니다.

 

그럼에도 다양한 사고와 알고리즘 풀이 능력을 키울 수 있었던 문제라고 생각합니다!