문제 링크 (opens new window)

풀이

1. BFS로 최단거리를 계산한다.
2. 방문 배열의 종류가 벽을 부순 여부와 부수지 않은 여부로 쪼개진다.
3. 중간에 벽을 부순 경우 해당 좌표로부터 BFS는 더 이상 벽을 부수지 못한다.
4. 벽 부숴서 도달하는 거리가 어차피 최단거리가 되므로 부순 방문배열부터 옵셔널 언래핑을 진행하여 출력한다.
5. 벽 부숴서, 안부숴서 둘다 도달하지 못한 경우 -1을 출력한다.

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let NM = readLine()!.split(separator: " ").map { Int($0)! }; let N = NM[0]; let M = NM[1]
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: M), count: N)
// key: 벽을 부순 회차
// value: 방문 위치
var visited: [Bool: [[Int]]] = [:]
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]

for i in 0..<N {
    adj[i] = readLine()!.map { Int(String($0))! }
}

var q = Queue<(Int, Int, Bool)>() // 좌표, 벽 부쉈는지
q.enqueue((0,0,false))
visited[true] = .init(repeating: .init(repeating: 0, count: M), count: N)
visited[false] = .init(repeating: .init(repeating: 0, count: M), count: N)
visited[false]?[0][0] = 1

while !q.isEmpty {
    guard let here = q.dequeue() else { break }

    for i in 0..<4 {
        let ny = dy[i] + here.0
        let nx = dx[i] + here.1

        if ny < 0 || nx < 0 || ny >= N || nx >= M || visited[here.2]![ny][nx] != 0 { continue }

        // 벽을 만났는데
        if adj[ny][nx] == 1 {
            // 벽을 이미 부쉈으면 더 이상 못부심
            if here.2 {
                continue
            } else {
                // 아직 벽을 안부쉈으면 벽 부수고 나아가기
                visited[true]![ny][nx] = visited[here.2]![here.0][here.1] + 1
                q.enqueue((ny, nx, true))
                continue
            }
        }

        visited[here.2]![ny][nx] = visited[here.2]![here.0][here.1] + 1
        q.enqueue((ny, nx, here.2))
    }
}

if let crashed = visited[true]?[N-1][M-1], crashed != 0 {
    print(crashed)
} else if let normal = visited[false]?[N-1][M-1], normal != 0{
    print(normal)
} else {
    print(-1)
}