프로그래머스 - 경주로 건설 (Kotlin)

프로그래머스 level3 - 경주로 건설 (코틀린)

 

문제 요약

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.

 

직선 도로는 100원, 커브길 도로는 500원이다.

 

---

제한사항

• board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
• board 배열의 각 원소의 값은 0 또는 1 입니다.
  • 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
  • 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
• board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
• 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

---

해설

이번 문제는 BFS/DP를 이용하여 해결해야 한다.

 

이 문제를 얼핏보면 단순히 최단경로를 찾는 문제로 착각할 수 있다.

하지만 이번 문제는 최단경로를 찾는 것이 아닌 최소비용 경로를 찾는 것이다.

 

이때 중요한 점은 3차원 배열을 이용해야 한다는 것이다.

 

3차원 배열을 사용하는 이유는 모든 방향을 고려하기 위하여 3차원 배열을 사용하는 것이다.

단순히 2차원 배열의 dp를 사용한다면 마지막 테스트케이스인 25번을 통과하지 못한다.

 

그 이유는 아래와 같다.

 

(벽)	(벽)	♡(2200)(↓)	2100(←)
2200(→)	☆(2300)(→)	♢(?)	(벽)
(벽)	(벽)	(벽)	(벽)
(벽)	(벽)	(벽)	(벽)

 

 

위의 표를 보자.

 

2차원 배열을 사용했을 때 ♢ 지점의 값은 어떻게 될까?

 

♢ = ☆(2300) + 100(직진) or ♡(2200) + 600(커브) = ☆(2400)

2차원 배열의 dp를 사용한다면 둘 중 최솟값인 2400(☆에서 온 값)의 값으로 갱신될 것이다.

 

그렇다면 이후에는 이 값을 사용하는 것이 정답일까?? 그렇지 않다.

 

♢ (☆2400) 을 사용하는 것이 현재 위치에서는 최솟값일지라도 다음좌표에서 최소비용을 보장할 수 없다.

다음 위치를 확인해보자.

 

(벽)	(벽)	♡(2200)(↓)	2100(←)
2200(→)	☆(2300)(→)	♢(2400)	(벽)
(벽)	(벽)	○	(벽)
(벽)	(벽)	(벽)	(벽)

 

♢ 바로 아래인 ○를 확인해보자.

 

우리는 이전의 작업을 통해 2400(→) 의 값을 구했다.

그렇다면 ○ = 2400 + 600(커브) = 3000이다.

 

이게 과연 최소값일까?

이전으로 돌아가서 ♡ 위치부터 다시 확인해보자.

♡ 위치에서 한칸 아래인 ♢ 위치는 2800 이다. (♡위치에서 커브)

다시 여기서 한칸 아래인 ○의 위치에서는 2900의 값이 나온다. (♢ 위치에서 직선)

 

○ 위치는 ☆에서 오는 것이 아닌 ♡ 에서 오는 것이 최소비용이 된다.

비록 ♢ 위치에서는 더 큰값이 들어갔지만 후에 최소비용이 된 것이다.

 

2차원 배열을 사용했기에 이 경우를 처리하지 못한 것이다.

즉, 이 모든 방향을 고려하기 위하여 우리는 3차원 배열을 사용해야 한다.

visited[x][y][z] 의 의미는 x, y 의 값은 z 방향에서 온 값을 의미한다.

 

그 이후에는 기본적인 bfs와 똑같이 구현하면 된다.

다만 여기서 dp방식을 사용해야 하기에 visited[x][y] == false 일 때 큐에 추가하는 것이 아닌
현재 위치에서 다음 방향의 비용을 구한 next 를 구하고 visited[nx][ny][i] >= next 일 때 큐에 추가해야 한다.

 

---

전체 코드

import java.util.*

class RacingRoad {
    //0, 2 : 가로 1, 4: 세로
    private val dx = intArrayOf(0, 1, 0, -1)
    private val dy = intArrayOf(1, 0, -1, 0)
    private val r = intArrayOf(0, 2)
    private val c = intArrayOf(1, 4)

    fun solution(board: Array<IntArray>): Int {
        data class Car(val x: Int, val y: Int, val cost: Int, val d: Int)

        //직선 1, 곡선 2
        var visited = Array(board.size) { Array(board.size) { Array(4) { Int.MAX_VALUE } } }
        val q: Queue<Car> = LinkedList()
        q.offer(Car(0, 0, 0, -1))

        while (q.isNotEmpty()) {
            val (x, y, c, d) = q.poll()

            for (i in 0..3) {
                val nx = x + dx[i]
                val ny = y + dy[i]

                val next = if (d == i || d == -1) {
                    c + 100
                } else {
                    c + 600
                }

                if (nx in board.indices && ny in board.indices && board[nx][ny] == 0 && visited[nx][ny][i] >= next) {
                    q.offer(Car(nx, ny, next, i))
                    visited[nx][ny][i] = next
                }

            }
        }

        return visited[board.size - 1][board.size - 1].min()
    }
}

fun main() {
    val rr = RacingRoad()
    println(
        rr.solution(
            arrayOf(
                intArrayOf(0, 0, 1, 0),
                intArrayOf(0, 0, 0, 0),
                intArrayOf(0, 1, 0, 1),
                intArrayOf(1, 0, 0, 0)
            )
        )
    )
}

 

---

정답

 

 

3시간 이상을 투자했음에도 해결하지 못하여 다른 사람의 코드를 보고 해결하였다.

2차원 배열을 사용해서 해결하려고 했으나 실패하여 다른 사람의 힌트를 보고 3차원 배열로 재구현 했음에도 실패했다.

다른 사람의 코드를 이해하는데에도 상당한 시간이 소요됐다.

문제만 보고 쉬울 줄 알았으나 너무 너무 어려웠따....😭