[Kotlin] 프로그래머스 경주로 건설

📘 문제

https://programmers.co.kr/learn/courses/30/lessons/67259

💡 풀이

1. 정리부터하면 조건에 맞게 bfs를 활용하여 목적지까지의 최단거리를 구하는 문제이다.
2. 주의할 점은 코너를 돌 때는 500원이 아니라 600원으로 계산해야한다. (그림을 잘 봐야합니다.)
3. bfs를 돌리며 최소비용을 확인해야하는데, 각 방향별로 비용을 저장해줘야한다.
4. 처음에는 단순히 현재 비용과 다음 비용을 계산하며 최솟값을 넣어줬다.
5. 근데 그렇게 하면 1)코너를 한 번 먼저 돌고(+600) 직선 한 번만 가면 되는 길이 있고(+100) =>700
6. 2)직선만 8번 가야될 때 => 800, 2)번이 목적지까지의 비용이 더 들지만 로직상 2)쪽으로 루프를 돌리게 되어 최소비용이 2)번이 된다.
7. 그러므로 3차원배열을 따로 만들어 각 방향별로 최소 비용을 저장해놓고 최종적으로 목적지 기준으로 각 방향에 대해 포문을 돌리며 최소 비용을 찾으면 된다.

💻 코드

import java.util.LinkedList
import java.util.Queue
import kotlin.math.min

private fun main() {
    solution(arrayOf(intArrayOf(0, 0, 0), intArrayOf(0, 0, 0), intArrayOf(0, 0, 0)))
}

private val goX = intArrayOf(0, 0, 1, -1) //우, 좌, 하, 상
private val goY = intArrayOf(1, -1, 0, 0)
private var answer = Int.MAX_VALUE
private lateinit var vis: Array<BooleanArray>
private lateinit var priceArr: Array<Array<IntArray>>

private fun solution(board: Array<IntArray>): Int {
    // 0 또는 1
    // 0은 비움 1은 벽
    // 0,0부터 n-1,n-1까지 경주로 건설 필요
    // 상 하 좌 우
    // 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로: 직선 도로
    // 직선 도로가 서로 직각으로 만나면 코너
    // 직선 도로 한 개: 100원
    // 코너: 500원 근데 600으로 처리해야함
    // 경주로 건설 최소 비용
    // 재방문 허용
    // bfs
    vis = Array(board.size) { BooleanArray(board.size) }
    // 방향, x,y
    priceArr = Array(4){Array(board.size) { IntArray(board.size) { Int.MAX_VALUE } }}
    bfs(board)
    for (i in 0 until 4){
        answer = min(answer, priceArr[i][board.lastIndex][board.lastIndex])
    }
    println(answer)
    return answer
}

private fun bfs(board: Array<IntArray>) {
    val n = board.size
    val queue: Queue<Road> = LinkedList()
    queue.add(Road(0, 0, 0, -1))
    vis[0][0] = true
    while (queue.isNotEmpty()) {
        val road = queue.poll()
        val (x, y, price, dir) = road
        
        for (i in 0 until 4) {
            var (nx, ny, nPrice, nDir) = intArrayOf(x + goX[i], y + goY[i], price, i)
            if (nx !in 0 until n || ny !in 0 until n) continue
            if (board[nx][ny]==1) continue
            if (dir == -1) nPrice += 100
            else if (dir != nDir) nPrice += 600
            else nPrice += 100

            if (!vis[nx][ny] || priceArr[nDir][nx][ny] >= nPrice) {
                vis[nx][ny] = true
                priceArr[nDir][nx][ny] = nPrice
                queue.add(Road(nx, ny, nPrice, nDir))
            }
        }
    }
}

data class Road(val x: Int, val y: Int, val price: Int, val dir: Int)

결과