<백준> 녹색 옷 입은 애가 젤다지?(Gold 4)

[백준]

4485번: 녹색 옷 입은 애가 젤다지?

[깃허브]

ForCodeKata/baekjoon 문제집/녹색 옷 입은 애가 젤다지? at main · heesoo-park/ForCodeKata

제출 결과

---

 

거의 다 풀었다고 생각한 문제였다.

문제를 보자마자 최소 비용 경로가 나오고 저번에 풀었던 택배 배송 문제가 생각나면서 다익스트라 알고리즘을 써야겠다는 생각이 들었기 때문이다.

하지만 이번에는 인접 리스트를 사용할 수 있는 형태가 아니어서 고민을 하다가 순수 BFS로 방향을 약간 틀어보았다.

 

BFS로 코드를 짜고 있는데 생각해보니까 '지금까지 했던 BFS로 하면 한번 방문한 칸은 다시 갈 수 없는데 최소 비용 갱신을 하려면 다시 방문해야할 때도 있어서 어떡하지...?'라는 생각이 들더라

그러다 알게 된 건 Boolean 값을 저장하지말고 계산 결과값을 저장하는 Int 배열로 선언하는 것이었다.

그렇게 하면 방문 안 했을 때는 그냥 값을 넣고 방문 했을 때는 현재 경로가 더 최소 비용일 때 값을 갱신하면 되기 때문이다.

이렇게 흐뭇하게 코드를 짜고 제출했는데 시간초과가 났다...?!?!

숫자 제한도 작고 재귀함수도 아닌데 이렇게 시간초과가 나서 얼이 빠졌는데... 끝내 알지 못해 백준에 질문만 남겨놨다.

이후에 여러 코드를 보면서 왜 안 될까 했지만 다른 점이 없었다...

 

그러다 통과한 방법은 아주 간단했다.

다익스트라 알고리즘을 거의 적용한 것과 다름 없는 상황에서 큐를 우선순위큐로 바꾸는 것이었다.

이를 위해 Data Class에 cost 변수를 추가했고 cost를 기준으로 오름차순 정렬이 되도록 우선순위 큐를 선언했다.

이렇게 하면 cost 값이 작은 게 먼저 진행되기 때문에 이후에 오는 값들은 새로운 루트가 아니면 다 조건문에 걸려 가지치기가 될 것이다.(나의 생각)

그래서 큐에서 우선순위큐로 바꾸기만 했는데 통과했다고 생각한다.

큐로 하면 모든 걸 다 일일이 비교하고 바꾸고 하는 과정이 빈번히 일어났을 테니까...

 

여기서 알게 된 건 다익스트라 알고리즘을 사용할 때 인접 리스트 형태 말고 2차원 배열에서 진행하는 방법과 BFS처럼 진행시키는 방법이다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.PriorityQueue

const val INF = 987654321

val cave = Array(125) { IntArray(125) { 0 } }
val calRoute = Array(125) { IntArray(125) { INF } }

val dy = intArrayOf(0, 1, 0, -1)
val dx = intArrayOf(1, 0, -1, 0)

data class Pos(
    val y: Int,
    val x: Int,
    val cost: Int
)

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var cnt = 1
    while (true) {
        val n = readln().toInt()
        if (n == 0) break

        resetValue()
        for (i in 0 until n) {
            val line = readln().split(' ').map { it.toInt() }
            for (j in 0 until n) {
                cave[i][j] = line[j]
            }
        }

        bfs(n)
        bw.write("Problem ${cnt++}: ${calRoute[n - 1][n - 1]}\n")
    }

    bw.flush()
    bw.close()
}

fun resetValue() {
    for (i in 0 until 125) {
        for (j in 0 until 125) {
            calRoute[i][j] = INF
        }
    }
}

fun bfs(size: Int) {
    val q = PriorityQueue<Pos> { p1, p2 ->
        when {
            p1.cost > p2.cost -> 1
            p1.cost < p2.cost -> -1
            else -> 0
        }
    }

    q.offer(Pos(0, 0, cave[0][0]))
    calRoute[0][0] = cave[0][0]

    while (q.isNotEmpty()) {
        val cur = q.poll()

        for (i in 0 until 4) {
            val newR = cur.y + dy[i]
            val newC = cur.x + dx[i]

            if (newR !in 0 until size || newC !in 0 until size) continue
            if (calRoute[newR][newC] <= calRoute[cur.y][cur.x] + cave[newR][newC]) continue

            calRoute[newR][newC] = calRoute[cur.y][cur.x] + cave[newR][newC]
            q.offer(Pos(newR, newC, calRoute[newR][newC]))
        }
    }
}