[백준/Swift] 1261: 알고스팟

 

1261번: 알고스팟

간단한 문제 요약

시작 (1,1) 탈출 칸 (N,M). 시작 칸에서부터 미로를 탈출해야 한다. 벽이 있는 경우 벽을 부수면서 탈출해야 하는데 벽을 최소한으로 부숴서 탈출 지점까지 도착해야 한다.

문제 풀이, 느낀 점

  문제 선정은 다익스트라 파트에서 골랐다. 당연히 힙을 구현했고 힙을 이용해서 풀었다. 한 가지 낯설었던 것은 기존에 다익스트라 문제는 지점을 지날 때 가중치 값이 주어지는데 이 문제는 가중치가 없었다. 그래서 이전에 방문했던 칸을 다시 탐색하면 어쩌지 하는 생각이 잠시 있었는데 초기 visited배열을 전부 Int.max로 선언하고 특정 현재 위치 + 1 or 현재 위치에서 벽을 부순 횟수를 가지고 탐색을 하면 이전에 탐색했던 지점을 안 갈 것이라는 생각이 들었다.'

 

 예전에 벽 부수고 이동하기 문제 풀이와 비슷하게 푼 분들도 있었는데 난 시간 초과가 날 까봐 힙을 선택한 것이다. 문제 풀고 다른 분들의 풀이를 봤다. 일반적인 배열의 Element에 벽을 부순 횟수를 기록해 나갔다. 나도 물론 큐를 통해 저장하긴 했지만,, 근데 Deque를 사용한 분들이 몇 있었다. Deque도 공부 해봐야 겠다.

코드

//MARK: - Properties
var (width, height) = (0,0)
var map = [[Int]]()
var visited = [[Int]]()
var start: Point = (-1,-1)
var end: Point = (-1,-1)

//MARK: - Helpers
func input() {
    let wh = readLine()!.split{$0==" "}.map{Int(String($0))!}
    width = wh[0]
    height = wh[1]
    map = Array(repeating:[Int](),count:height)
    visited = Array(repeating:Array(repeating: Int.max,count: width), count:height)
    (0..<height).forEach{ i in
        let input = readLine()!.map{Int(String($0))!}
        map[i] = input
    }
    start = (0,0)
    end = (width-1,height-1)
}

func isOutOfBounds(point:Point) -> Bool {
    return point.x < 0 || point.x > width-1 || point.y < 0 || point.y > height-1
}

func dijkstra() {
    var priority = Heap<Node>()
    priority.insert(Node(point: start, breakCnt: 0))
    visited[start.y][start.x] = 0
    while !priority.isEmpty {
        guard let curNode = priority.delete() else {
            break
        }
        if curNode.breakCnt > visited[curNode.y][curNode.x] {
            continue
        }
        for (dx,dy) in Direction {
            let (nx,ny) = (curNode.x+dx,curNode.y+dy)
            if isOutOfBounds(point: (nx,ny)) { continue }
            if visited[ny][nx] > visited[curNode.y][curNode.x] {
                if map[ny][nx] == 0 {
                    visited[ny][nx] = visited[curNode.y][curNode.x]
                    priority.insert(Node(point: (nx,ny), breakCnt: visited[ny][nx]))
                } else if map[ny][nx] == 1 && visited[ny][nx] > curNode.breakCnt + 1 {
                    visited[ny][nx] = visited[curNode.y][curNode.x] + 1
                    priority.insert(Node(point: (nx,ny), breakCnt: visited[ny][nx]))
                }
            }
        }
    }
}

func solution() {
    input()
    dijkstra()
    print(visited[end.y][end.x])
}

solution()

struct.. Heap, Node etc

//MARK: - Model
struct Heap<T> where T: Comparable {
    private var list = [T]()
    private let isLeftSmall: (T,T) -> Bool
    init(isLeftSmall: @escaping (T, T) -> Bool) {
        self.isLeftSmall = isLeftSmall
    }
    init() {
        self.init(isLeftSmall: <)
    }
}
extension Heap {
    var isEmpty: Bool {
        return list.isEmpty
    }
    var count: Int {
        return list.count
    }
}
extension Heap {
    mutating func insert(_ element: T) {
        var idx = list.count
        list.append(element)
        while idx < list.count && isLeftSmall(list[idx],list[(idx-1)/2]) {
            list.swapAt(idx, (idx-1)/2)
            idx = (idx-1)/2
        }
    }
    mutating func delete() -> T? {
        guard !isEmpty else {
            return nil
        }
        guard count != 1 else {
            return list.popLast()
        }
        let element = list.first!
        var idx = 0
        list.swapAt(idx, count - 1)
        _ = list.removeLast()
        while idx < count {
            let (left,right) = (idx*2+1,idx*2+2)
            if right < list.count {
                if isLeftSmall(list[left],list[right]) && isLeftSmall(list[left], list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else if isLeftSmall(list[right],list[idx]) {
                    list.swapAt(right, idx)
                    idx = right
                } else {
                    break
                }
            } else if left < list.count {
                if isLeftSmall(list[left], list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else {
                    break
                }
            } else {
                break
            }
        }
        return element
    }
}

typealias Point = (x:Int,y:Int)
let Direction = [(-1,0),(1,0),(0,1),(0,-1)]

struct Node {
    private var point: Point
    var breakCnt: Int
    init(point: Point, breakCnt: Int) {
        self.point = point
        self.breakCnt = breakCnt
    }
    var x: Int {
        return point.x
    }
    var y: Int {
        return point.y
    }
}
extension Node: Comparable {
    static func <(lhs:Node, rhs:Node) -> Bool {
        return lhs.breakCnt < rhs.breakCnt
    }
    static func ==(lhs:Node,rhs:Node) -> Bool {
        return lhs.point == rhs.point
    }
}