[백준 4485번] [Kotlin] 녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485

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

 

난이도 : 골드 4
태그 : 그래프 이론, 데이크스트라

 

 

설명

다익스트라를 응용해야 하는 것은 쉽게 알아챌 수 있었지만,

상하좌우 탐색를 해야 하는 탐색에서 어떻게 구현하냐 고민을 많이 했습니다.

어음.. 다익스트라가 아니라 BFS를 사용해야 하나? 하는 마음에 질문게시판을 뒤적거려봤는데,

다익스트라 + BFS를 연상케 하는 형태로 풀 수 있었습니다

 

 

소스코드

import java.util.*

data class Node(val x: Int, val y: Int, val weight: Int) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return this.weight - other.weight
    }
}

lateinit var map: Array<Array<Int>>
lateinit var table: Array<Array<Int>>
const val MAX_VALUE = 987654321
var n = 0
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

fun main() = with(System.`in`.bufferedReader()) {

    val sb = StringBuilder()
    var caseIdx = 1

    while (true) {
        n = readLine().toInt()
        if (n == 0) break

        map = Array(n) { StringTokenizer(readLine()).let { st -> Array(n) { st.nextToken().toInt() } } }
        table = Array(n) { Array(n) { MAX_VALUE } }

        dijkstra()
        sb.append("Problem ${caseIdx++}: ${table[n - 1][n - 1]}\n")
    }

    print(sb)
}


fun dijkstra() {
    val pq = PriorityQueue<Node>()
    table[0][0] = map[0][0]

    // 0, 0 부터 탐색 시작
    pq.offer(Node(0, 0, map[0][0]))

    while (pq.isNotEmpty()) {
        val target = pq.poll()

        // 상하좌우 탐색
        for (i in 0 until 4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]

            if (nx !in 0 until n || ny !in 0 until n) continue

            if (table[nx][ny] > table[target.x][target.y] + map[nx][ny]) {
                table[nx][ny] = table[target.x][target.y] + map[nx][ny]
                pq.offer(Node(nx, ny, table[nx][ny]))
            }
        }
    }
}

 

코드 분석

1. n, 맵 정보, 상하좌우 이동을 도와줄 dx, dy 세팅
2. 0, 0에서 다른 모든 점으로 갈 수 있는 최단경로 비용을 담을 table을 생성하고, 무한대 값(여기서는 987654321)로 초기화한다.
3. 다익스트라 수행
   1. 여기서는 우선순위 큐<Node>를 사용해 개량된 다익스트라를 사용한다.
   2. 커스텀 데이터 클래스인 Node를 사용하며, Node(x,y,weight)는 0,0 부터 x,y까지 weight만큼의 비용이 든다는 의미이다.
      1. Compable을 상속하여 compareTo 메소드를 오버라이딩 해 weight 기준으로 정렬 기준을 설정한다.
   3. 첫 번째 값으로 우선순위 큐에 0,0 그리고 0,0으로 가는 시작비용인 map[0][0]을 넣는다.
   4. 큐가 빌 때까지 상하좌우 탐색을 진행하며, 0,0부터 다음 목적지까지 가는 기존의 비용(table[nx][ny]) 보다, 0,0 부터 직전의 점으로 가는 비용 + 직전 점 부터 다음 점으로 가는 비용(table[target.x][target.y] + map[nx][ny])이 더 저렴하다면 갱신한다. (table[nx][ny] = table[target.x][target.y] + map[nx][ny]

 

 

 

후기

수 많은 고뇌와 먼저 푼 사람들의 조언 덕분에 BFS와 다익스트라를 섞은 듯한 코드가 나왔습니다.

다익스트라 같은 경우는 굉장히 유명한 알고리즘이고, 몇 번 관련 문제를 풀어보기도 했지만

코딩테스트에선 그리 자주 접하지 않아 쓰는 법이 가물가물해 더욱 해맸던 것 같습니다.

다시 최단경로 문제나 한 번 더 풀고 와야겠네요.