프로그래머스[programmers] - 경주로 건설(Kotlin)[LV3]

문제

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

프로그래머스

 

문제 풀이

전형적인 BFS 문제이다.

BFS 문제에서의 난이도는 방문배열을 3차원배열로 해야 하는지, 2차원 배열로 해야 하는지에 따라 나뉜다고 생각한다.

해당 문제는 좌표로 들어왔던 도로의 방향을 기억해줘야 한다. 그래야 코너를 만들 때 계산을 해 줄 수 있기 때문이다.

그리고 도착지점에 도착할 경우 그때 경주로 건설에 사용한 비용의 최소값을 반환해야 한다. 

따라서 나는 우선순위큐를 이용해서 경주로 건설에 사용한 비용을 오름차순으로 정렬하고, BFS를 진행했다.

그러면 도착지점에 도착한 순간 최소비용이 보장되어 있기에, 도착했다면 함수를 종료하면 된다.

 

방문을 검사하는 배열은 3차원 배열로 설정했다.

N*N*4로 설정했는데, 4인 이유는 방향이 상하좌우 4방향이기 때문이다.

왜 우선순위큐를 사용했는데, 방문처리를 해야하냐고 의아해할 수도 있다.

다음과 같은 경우가 생기기 때문에 나는 방향을 추가한 방문배열을 만들었다.

다음과 같은 경우 (1,1)로 가는데 700원이라는 비용이 공통적으로 발생한다.

하지만 (0,0) -> (0,1) -> (1,1) -> (1,2)로 가면 2개의 코너가 생긴다.

하지만 그림과 같이 (0,0) -> (1,0) -> (1,1) -> (1,2)로 가면  1개의 코너가 생긴다.

따라서 방향별로 체크를 해줘야 하는것이다.

똑같은 비용으로 (1,1)을 가지만, 방향에 따라서 결과가 달라지기 때문이다.

이 정도까지 생각했으면 그다음부터는 다른 BFS 문제와 동일하게 진행을 하면 된다.

 

import java.util.*

class Solution {

    val x = listOf(-1, 1, 0, 0)
    val y = listOf(0, 0, 1, -1)
    var answer = 100000000
    private val pq = PriorityQueue<Road>(compareBy({ +it.price }))
    fun solution(board: Array<IntArray>): Int {
        bfs(board)
        return answer
    }

    fun bfs(board: Array<IntArray>) {
        var start = Pair(0, 0)
        val n = board.size
        val end = Pair(n - 1, n - 1) // 도착지점
        var visit = Array(n) { Array(n) { Array(4) { false } } } //n*n*4 3차원 방문 배열 생성
        for (i in 0 until 4) { // 방향 별로 초기 설정
            pq.add(Road(start, 0, i))
        }
        while (!pq.isEmpty()) {
            var cur = pq.poll()
            if (visit[cur.loc.first][cur.loc.second][cur.dir]) //방문한 경우
                continue
            if (cur.loc == end) { //도착할 경우
                answer = cur.price
                return
            }
            visit[cur.loc.first][cur.loc.second][cur.dir] = true //방문 처리
            for (d in 0 until x.size) {
                var mx = cur.loc.first + x[d]
                var my = cur.loc.second + y[d]
                if (mx !in board.indices || my !in board.indices) //이동하는 좌표가 배열의 범위를 벗어난 경우
                    continue
                if (visit[mx][my][d] || board[mx][my] == 1) //방문했거나, 벽인 경우
                    continue
                if (d == cur.dir) { //방향이 일치할때
                    pq.add(Road(Pair(mx, my), cur.price + 100, d))
                } else { //방향을 꺾어야 할 때
                    pq.add(Road(Pair(mx, my), cur.price + 600, d))
                }
            }
        }
    }

    data class Road(var loc: Pair<Int, Int>, var price: Int, var dir: Int)
}