[PS][Programmers][Swift] 미로 탈출

문제를 풀면서..

카카오에서 이번 인턴 문제를 정말 이를 갈고 냈다는것을 다시 한번 확인할수 있었다.
크게 범주를 합쳐보자면 비트 마스킹 + 다익스트라가 아닐까 싶다.

백준 문제로 치자면 플레 5에서 골드 1정도 일텐데, 이런걸 시험장에서 풀면 아마도 머리가 하얘질것 같다.

풀이 방식

1. 간선 정보를 먼저 생각해둔다.
   1 - 1. 간선 정보는 row로 start 포인트, (목적지, 비용, 역방향 인지)
2. 다익스트라에서 사용할 Bit 크기대로 visit 배열 구현
   2- 1. visit 배열은 row를 traps의 전체 비트 크기수를 가져올수 있을만큼의 크기로 선언한다.
   2- 2. 문제에서는 (1 << traps.count) 크기만큼 구성해두었다.
3. 다익스트라 구현
   3- 1. 현재 위치가 traps에 해당하는지 확인한다.
   3- 2. 만약 traps에 해당한다면 스위치를 눌러준다.
   3- 3. trapinfo 를 가지고, choicedir를 통해 정,역인지 방향을 선택한다.
   3- 4. 모든 정보를 충족하는 다음 방향의 간선을 선택하여 pq에 push 해준다.

코드는 다음과 같다.

import Foundation

var pq : [(Int,Int, Int)] = [(Int, Int, Int)](repeating: (0,0, 0), count: 100001)
var idx = 0
func compare(_ a: Int, _ b :Int) -> Bool {
    return pq[a].0 <= pq[b].0
}
func push(_ inp: (Int, Int, Int)) {
    var c = 0
    var p = 0
    idx += 1
    pq[idx] = inp
    c = idx; p = c / 2
    while p >= 0, !compare(p, c) {
        let temp = pq[c]; pq[c] = pq[p]; pq[p] = temp
        c = p; p = c / 2
    }
}

func pop() {
    pq[1] = pq[idx]
    idx -= 1
    var p = 1; var l = 2; var r = 3; var c = 0
    while l <= idx {
        if r > idx {
            c = l;
        }else { c = compare(l, r) ? l: r}
        if compare(p, c) {break}
        let temp = pq[p]; pq[p] = pq[c]; pq[c] = temp;
        p = c; l = p * 2; r = l + 1
    }
}

var mapping: [Int: Int] = [Int: Int]()
var map: [[(Int, Int, Bool)]] = []
var visit: [[Int]] = []
func choicedir(_ bit: Int, _ id1: Int, _ id2: Int) -> Bool {
    var v1 = 0
    var v2 = 0
    if mapping[id1] != nil {
        if bit & (1 << mapping[id1]!) > 0 {
            v1 = 1
        }
    }
    if mapping[id2] != nil {
        if bit & (1 << mapping[id2]!) > 0 {
            v2 = 1
        }
    }
    if v1 == v2 {
        return false
    }
    return true
}
func dijkstra(_ start: Int, _ end: Int) {
    var bit = 0
    if mapping[start] != nil {
        bit |= (1 << mapping[start]!)
    }
    visit[0][start] = 0
    push((0, start, bit))
    while idx != 0 {
        let now = pq[1].1
        let nowCost = pq[1].0
        var trapInfo = pq[1].2
        if mapping[now] != nil {
            let bitinfo = (1 << mapping[now]!)
            if trapInfo & bitinfo > 0{
                trapInfo -= bitinfo
            }else {
                trapInfo |= bitinfo
            }
        }
        pop()
        for road in map[now] {
            let next = road.0
            if choicedir(trapInfo, now, next) != road.2 { continue }
            let nextCost = road.1 + nowCost
            if visit[trapInfo][next] > nextCost {
                visit[trapInfo][next] = nextCost
                push((nextCost, next, trapInfo))
            }
        }
    }
}

func solution(_ n:Int, _ start:Int, _ end:Int, _ roads:[[Int]], _ traps:[Int]) -> Int {
    let INF = 987654321
    let l2 = [Int](repeating: INF, count: n + 1)
    visit = [[Int]](repeating: l2, count: (1 << traps.count) )
    for i in 0..<traps.count {
        mapping[traps[i]] = i
    }
    let layer = [(Int, Int, Bool)]()
    for _ in 0...n {
        map.append(layer)
    }
    
    for road in roads {
        let s = road[0]
        let e = road[1]
        let c = road[2]
        map[s].append((e,c, false))
        if mapping[s] != nil || mapping[e] != nil {
            map[e].append((s, c, true))
        }
    }
    dijkstra(start, end)
    var ans = INF
    for i in 0...(1 << traps.count)-1 {
        if ans > visit[i][end] {
            ans = visit[i][end]
        }
    }
    return ans
}

아쉬운 점

1. Swift에서 Priority Queue를 구현하는걸 몰라서 C에서 하던 버릇을 못버리고 C스타일의 힙을 구현했다.
2. 의미있는 네이밍을 하고싶었는데.. mapping이랑 map은 적절하지 못했던것 같다.
3. choicedir이 깨끗하지 못하다.