[프로그래머스] 2020 카카오 인턴쉽 경주로 건설 with Kotlin

문제

크기가 n*n인 1과 0으로 이루어진 2차원 배열이 주어진다.

시작은 0,0 이며 도착지는 n-1, n-1 이다.

 

1은 벽으로 이루어져있어 지나갈 수 없고, 직선은 100의 비용이, 코너는 500의 비용이 소모된다.

시작부터 도착지점까지 도로를 건설한다고 할 때, 건설할 수 있는 최소 비용의 금액을 반환하여라.

 

자세한 문제는 프로그래머스에서

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

프로그래머스

 

 풀이 과정

1. 벽을 끼고 도착지까지의 최소 거리를 구하는 문제의 경우 DFS보다 BFS가 효율적이다.
   1. 실제로 DFS를 써도 풀 수는 있지만 절반이 시간초과가 나옴
2. 일방적인 방법으로 BFS를 사용하면 25번 테스트케이스에서 실패가 나온다.
   1. 일방적인 방법이란 >> 방문한 인덱스별로 최소비용을 저장한 뒤 비용이 크면 pass 작으면 방문
   2. 실패가 나오는 이유는 A와 B의 경로가 있고, (1,3)의 교차로에서 (1,4)로 이동해야한다고 가정
      1. A는 코너를 끼고 이동하며, B는 직선으로 이동
      2. (1,3)에서 A 경로의 비용이 1500이라고 가정하고, B의 경로는 1700이라고 한다.
      3. 이때 (1,3)에서는 A가 저렴하지만 (1,4)의 경우 A는 코너를 끼고 이동하기 때문에 2100원의 비용이 발생하고, B의 경우 직선이기 때문에 1800원의 비용이 발생한다.
      4. B가 더 저렴한 경로지만 (1,3)에서 A가 저렴하여 B가 pass 되는 경우가 나와 실패
3. 직선은 100원, 코너는 코너를 끼고 직선이 하나 더 생기므로 600원
4. 방문 처리를 기존에 주어진 2차원 board가 아닌 경로(상하좌우)에 대한 방문 처리를 포함한 3차원 배열로 선언 (핵심)
   
   1. Array(n) { Array(n) { IntArray(4) { Int.MAX_VALUE / 2 } } } // n은 board의 크기 
5. 인덱스 별 방문 경로에 따른 비용을 저장하여 도착지 인덱스의 비용 중 가장 저렴한 비용을 반환한다.

 

코드

import java.util.*

data class Car(val x: Int, val y: Int, val cost: Int, val dir: Int)
class Solution {
    fun solution(board: Array<IntArray>): Int {
        val n = board.size
        val queue: Queue<Car> = LinkedList()
        // 핵심 (각각의 인덱스마다 들어오는 경로(상하좌우)에 따른 비용을 저장)
        val visited = Array(n) { Array(n) { IntArray(4) { Int.MAX_VALUE / 2 } } } 
        
        queue.add(Car(0,0,0,-1))
        
        val dx = arrayOf(-1, 1, 0, 0)
        val dy = arrayOf(0, 0, -1, 1)
        
        while(queue.isNotEmpty()){
            val (x, y, cost, dir) = queue.poll()
            
            for(i in 0..3){
                val mx = x + dx[i]
                val my = y + dy[i]
                
                // i가 dir의 경로와 같다면 직선 아니면 코너 
                val nc = if(dir == i || dir == -1) cost + 100 else cost + 600
            
                //배열을 안벗어나고, 다음 경로가 1이 아니라면
                if(mx in 0 until n && my in 0 until n && board[mx][my] != 1){
                    if(visited[mx][my][i] >= nc){
                        visited[mx][my][i] = nc
                        queue.add(Car(mx, my, nc, i))
                    }
                }
            }
        }
        
        // 도착지에서 4가지 경로 중 가장 비용이 적은 값 반환
        return visited[n-1][n-1].minOf{it}
    }

}