백준 28450번
https://www.acmicpc.net/problem/28450

문제

---

생각하기

---

• DP를 통해서도 풀 수 있고,

• 다익스트라 방식으로 BFS로도 풀 수 있는 문제이다

동작

결과

코드

---

Kotlin

DP

import java.io.*
import java.util.*
import kotlin.math.min

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0
private var H = 0

private lateinit var memo: Array<LongArray>

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    for (n in N - 1 downTo 0) {
        for (m in M - 1 downTo 0) {
            if (n == N - 1 && m == M - 1) {
                // 처음 시작은 통과
                continue
            }

            when {
                n == (N - 1) -> {
                    memo[n][m] += memo[n][m + 1]
                }

                m == (M - 1) -> {
                    memo[n][m] += memo[n + 1][m]
                }

                else -> {
                    memo[n][m] += min(memo[n + 1][m], memo[n][m + 1])
                }
            }
        }
    }

    if (memo[0][0] > H) {
        sb.append("NO")
    } else {
        sb.append("YES").append('\n').append(memo[0][0])
    }

    return sb.toString()
} // End of solve()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        M = nextToken().toInt()
    }

    memo = Array(N) { LongArray(M) }
    for (i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            for (j in 0 until M) {
                memo[i][j] = nextToken().toLong()
            }
        }
    }

    H = br.readLine().toInt()
} // End of input()

BFS

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private const val INF = Int.MAX_VALUE
private var N = 0
private var M = 0
private var H = 0

private lateinit var map: Array<IntArray>
private val dirX = arrayOf(1, 0) // 이동방향은 오른쪽또는 아래쪽으로만 가능
private val dirY = arrayOf(0, 1)

private data class Coordinate(var x: Int, var y: Int, var sum: Int) : Comparable<Coordinate> {
    override fun compareTo(other: Coordinate): Int {
        return sum - other.sum
    } // End of compareTo()
} // End of Coordinate class

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val ret = BFS()
    if (ret == INF) {
        sb.append("NO")
    } else {
        sb.append("YES").append('\n').append(ret)
    }

    return sb.toString()
} // End of solve()

private fun BFS(): Int {
    val que = PriorityQueue<Coordinate>()
    val isVisited = Array(N) { IntArray(M) { INF } }

    que.offer(Coordinate(0, 0, 0))
    isVisited[0][0] = map[0][0]

    while (que.isNotEmpty()) {
        val pollCoor = que.poll()

        repeat(2) { idx ->
            val nextX = dirX[idx] + pollCoor.x
            val nextY = dirY[idx] + pollCoor.y

            if (rangeCheck(nextX, nextY)) {
                val nextSum = pollCoor.sum + map[nextX][nextY]
                if (nextSum <= H) {
                    if (isVisited[nextX][nextY] > isVisited[pollCoor.x][pollCoor.y] + map[nextX][nextY]) {
                        isVisited[nextX][nextY] = isVisited[pollCoor.x][pollCoor.y] + map[nextX][nextY]
                        que.offer(Coordinate(nextX, nextY, isVisited[nextX][nextY]))
                    }
                }
            }
        }
    }

    return isVisited[N - 1][M - 1]
} // End of BFS()

private fun rangeCheck(nextX: Int, nextY: Int): Boolean {
    return nextX in 0 until N && nextY in 0 until M
} // End of rangeCheck()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        M = nextToken().toInt()
    }

    map = Array(N) {
        StringTokenizer(br.readLine()).run {
            IntArray(M) {
                nextToken().toInt()
            }
        }
    }

    H = br.readLine().toInt()
} // End of input()