간단한 문제 요약
시작 (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
}
}
'백준 PS일지 > Dijkstra' 카테고리의 다른 글
[백준/Swift] 11779: 최소비용 구하기 PS일지 (0) | 2023.01.11 |
---|---|
[백준/Swift] 1504: 특정한 최단 경로 (0) | 2023.01.09 |
[백준/Swift] 4482 : 녹색 옷 입은 애가 젤다지? (2) | 2023.01.07 |
[백준/Swift] 1238 : 파티/ 우선순위 큐 개념 정리, 최소 힙 개념 with 라이노님 Heap 정리 (2) | 2023.01.06 |