https://school.programmers.co.kr/learn/courses/30/lessons/67259
맨 왼쪽 위 (0, 0)위치에서 맨 오른쪽 아래 까지 최소 비용으로 경로를 생성하는 문제이다.
직선 도로는 100원, 코너는 500원의 비용이 든다.
위처럼 도로를 건설할 경우 직선도로 1~6까지 6개 + 코너(동그라미) 4개 = 600 + 2000 = 2600원의 비용이 든다.
cost를 기준으로 하는 Priority Queue를 이용한 bfs로 풀이를 시도했으나, 한 케이스에 대해 생각하지 못했고 이를 정리하려 한다.
풀이 방법은 아래와 같다.
enum class DIR{
VERTICAL,
HORIZONTAL
}
data class Pos(
val v: Int,
val h: Int,
val dir: DIR,
val cost: Int = 0
)먼저 위처럼 bfs에 사용될 두 클래스를 생성한다.
DIR은 현재 세로로 이동하는 상태인지, 가로로 이동하는 상태인지를 나타낸다.
Pos는 현재 세로 위치(v), 가로 위치(h), 방향(DIR), 비용을 나타낸다.
시작점에서 세로로 출발하는 경우와 가로로 출발하는 경우를 각각 계산해서 더 적은 코스트를 정답으로 하였다.
bfs 도중 비용을 계산하는 방법은 다음과 같다.
현재 VERTICAL 상태일 경우 - 위 or 아래로 움직일 때 cost +100, 왼쪽 or 오른쪽으로 움직일 때 cost +600 (직선1 + 코너1).
현재 HORIZONTAL 상태일 경우 - 왼쪽 or 오른쪽으로 움직일 때 cost +100, 위 or 아래로 움직일 때 cost +600 (직선1 + 코너1)
이런 방법으로 bfs를 진행해 (N-1, N-1)에 도착하면 바로 정답으로 하려 했다.
하지만 이 방법에는 빈틈이 존재했다.
위 상태처럼 두 위치에서 (3, 2)위치를 확장하려고 하는 경우이다.
Priority Queue이므로 cost가 적은 3900(HOR) 상태를 먼저 확장하게 되지만, (4, 2)에는 cost 4000(VER)인 상태가 더 비용이 싸진다.
Cost값 뿐만아니라 그 상태에서의 HORIZONTAL, VERTICAL 상태도 영향을 줄 수 있는 것이다.
따라서 방문 체크에 대한 로직을 변경하기로 했다.
방문 체크를 이차원 Int배열 2개를 사용하여, HORIZONTAL 상태와 VERTICAL 상태의 Cost를 각각 저장하고 갱신하는 방법이다.
그렇게 하면 위 예시의 (3, 2)에 대해 visitedV[3][2]에는 4100 (Cost 4000 위치에서 아래로 이동) visitedH[3][2]에는 4000 (Cost 3900위치에서 우측으로 이동)이 각각 저장된다.
즉 (3, 2)에 대해 (3, 2, VER, 4100) 상태와 (3, 2, HOR, 4000) 상태가 모두 존재한다.
이후 (4, 2)로 확장할 때 (3, 2, VER, 4100)상태와 (3, 2, HOR, 4000)상태 모두 아래 방향(VER)으로 확장한다.
Priority Queue에 의해서 (3, 2, HOR, 4000)상태를 먼저 꺼내오게 되고 (4, 2)로 확장하면 (4, 2, VER, 4600)이 되어 visitedV[4][2] = 4600이 된다.
다음으로 (3, 2, VER, 4100)을 꺼내와 (4, 2)로 확장하면 (4, 2, VER, 4200)이 되어 visitedV[4][2] = 4200으로 갱신하게 된다.
다음으로 또 Priority Queue에 의해서, 4200 Cost인 케이스를 먼저 확장하게 되며, 4600 Cost인 케이스는 이후 4200 Cost로 확장한 케이스보다 비용이 더 들어 확장할 수 없게 되어 최적을 보장한다.
class Solution {
val dirs = intArrayOf(-1, 0, 1, 0, -1)
fun solution(board: Array<IntArray>): Int {
return min(getSolution(DIR.VERTICAL, board), getSolution(DIR.HORIZONTAL, board))
}
fun getSolution(startDir: DIR, board: Array<IntArray>): Int{
val N = board.size
val pq = PriorityQueue<Pos>{p1, p2 -> p1.cost - p2.cost}
val visitedV = Array(N){IntArray(N){Int.MAX_VALUE}}
val visitedH = Array(N){IntArray(N){Int.MAX_VALUE}}
pq.offer(Pos(0, 0, startDir))
if(startDir == DIR.VERTICAL) visitedV[0][0] = 0 else visitedH[0][0] = 0
var smallest = Int.MAX_VALUE
while(pq.isNotEmpty()){
val next = pq.poll()
if(next.dir == DIR.VERTICAL && visitedV[next.v][next.h] < next.cost) continue
if(next.dir == DIR.HORIZONTAL && visitedH[next.v][next.h] < next.cost) continue
if(next.dir == DIR.VERTICAL)
visitedV[next.v][next.h] = next.cost
else
visitedH[next.v][next.h] = next.cost
if(next.v == N - 1 && next.h == N - 1){
if(smallest > next.cost)
smallest = next.cost
}
for(i in 0..3){
// 0위 1오른 2아래 3왼
val nv = next.v + dirs[i]
val nh = next.h + dirs[i + 1]
if(isInside(nv, nh, N) && board[nv][nh] != 1){
when{
i % 2 == 0 && next.dir == DIR.VERTICAL -> pq.offer(Pos(nv, nh, DIR.VERTICAL, next.cost + 100))
i % 2 == 1 && next.dir == DIR.HORIZONTAL -> pq.offer(Pos(nv, nh, DIR.HORIZONTAL, next.cost + 100))
i % 2 == 0 && next.dir == DIR.HORIZONTAL -> pq.offer(Pos(nv, nh, DIR.VERTICAL, next.cost + 600))
i % 2 == 1 && next.dir == DIR.VERTICAL -> pq.offer(Pos(nv, nh, DIR.HORIZONTAL, next.cost + 600))
}
}
}
}
return smallest
}
private fun isInside(v: Int, h: Int, N: Int) = v in 0 until N && h in 0 until N
}