[Algorithm] 백준 - 16933번 벽 부수고 이동하기 3 (Swift)

문제 소개

벽 부수기 시리즈! 이번에는 낮에만 블록을 깰 수 있다는 제약조건이 있다.

문제 풀이

시간 초과와 메모리 초과 때문에 좀 고생을 한 것 같다.

시간 초과

시간  초과의 경우 의외로 벽을 부시는 경우를 앞쪽에 둬서 해결이 되었다.

메모리 초과

최대한 요소를 늘리지 않으려고 했다. cost를 2로 나눈 나머지로 낮과 밤을 판별하니 메모리 초과가 나지 않았다.
 

큐를 구현하지 않고 풀이

import Foundation

let nmk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m, k) = (nmk[0], nmk[1], nmk[2])
let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)]

var map = [[Int]]()
var visit = Array(repeating: Array(repeating: Array(repeating: false, count: m), count: n), count: k + 1)

for _ in 0..<n {
    let line = Array(readLine()!).map { Int(String($0))! }
    map.append(line)
}

var queue: [(i: Int, j: Int, coin: Int, cost: Int)] = [(0, 0, k, 1)]
var idx = 0
visit[k][0][0] = true

while queue.count > idx {
    let popped = queue[idx]
    idx += 1
        
    if popped.i == n-1 && popped.j == m-1 {
        print(popped.cost)
        exit(0)
    }
        
    for d in ds {
        let i = popped.i
        let j = popped.j
        let ni = i + d.i
        let nj = j + d.j
        
        if 0..<n ~= ni && 0..<m ~= nj {
            if visit[popped.coin][ni][nj] { continue }
            
            if map[ni][nj] == 1 && popped.coin > 0 {
                if popped.cost % 2 == 1 {
                    visit[popped.coin][ni][nj] = true
                    queue.append((ni, nj, popped.coin - 1, popped.cost + 1))
                } else {
                    queue.append((i, j, popped.coin, popped.cost + 1))
                }
            }
            
            if map[ni][nj] == 0 {
                visit[popped.coin][ni][nj] = true
                queue.append((ni, nj, popped.coin, popped.cost + 1))
            }
        }
    }
}

print(-1)

 

큐를 구현하고 풀이

import Foundation

let nmk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m, k) = (nmk[0], nmk[1], nmk[2])
let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)]

var map = [[Int]]()
var visit = Array(repeating: Array(repeating: Array(repeating: false, count: m), count: n), count: k + 1)

for _ in 0..<n {
    let line = Array(readLine()!).map { Int(String($0))! }
    map.append(line)
}

struct DoubleStackQueue<Element> {
    private var inbox: [Element] = []
    private var outbox: [Element] = []
    
    var isEmpty: Bool{
        return inbox.isEmpty && outbox.isEmpty
    }
    
    init(_ array: [Element]) {
        self.inbox = array
    }
    
    mutating func enqueue(_ n: Element) {
        inbox.append(n)
    }
    
    mutating func dequeue() -> Element {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox = []
        }
        return outbox.removeLast()
    }
}

var queue = DoubleStackQueue([(i: 0, j: 0, coin: k, cost: 1)])
visit[k][0][0] = true

while !queue.isEmpty {
    let popped = queue.dequeue()
        
    if popped.i == n-1 && popped.j == m-1 {
        print(popped.cost)
        exit(0)
    }
        
    for d in ds {
        let i = popped.i
        let j = popped.j
        let ni = i + d.i
        let nj = j + d.j
        
        if 0..<n ~= ni && 0..<m ~= nj {
            if visit[popped.coin][ni][nj] { continue }
            
            if map[ni][nj] == 1 && popped.coin > 0 {
                if popped.cost % 2 == 1 {
                    visit[popped.coin][ni][nj] = true
                    queue.enqueue((ni, nj, popped.coin - 1, popped.cost + 1))
                } else {
                    queue.enqueue((i, j, popped.coin, popped.cost + 1))
                }
            }
            
            if map[ni][nj] == 0 {
                visit[popped.coin][ni][nj] = true
                queue.enqueue((ni, nj, popped.coin, popped.cost + 1))
            }
        }
    }
}

print(-1)

 

메모리 비교

속도차이는 거의 없다고 봐도 무방하고, 더블스택큐를 활용하니 메모리 사용량이 유의미하게 줄었다.