[백준] 삼각 그래프

Link : https://www.acmicpc.net/problem/4883

문제

이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다.

삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다.

오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 경로 중 아래로만 가는 경로의 비용은 7+13+3+6 = 29가 된다. 삼각 그래프의 간선은 항상 오른쪽 그림과 같은 형태로 연결되어 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 순서대로 주어진다. 비용은 정수이며, 비용의 제곱은 1,000,000보다 작다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 테스트 케이스 번호와 아래와 같은 형식으로 출력한다.

k. n

k는 테스트 케이스 번호, n은 최소 비용이다.

예제 입력 1

4
13 7 5
7 13 6
14 3 12
15 6 16
0

예제 출력 1

1. 22

1차 시도(BFS)

문제를 너무 가볍게 봤을때네느 그래프 탐색으로 풀 수 있을 것으로 생각을 했습니다. 그런데 BFS/DFS로 해결이 안되는 문제 였고 첫번때 시도는 실패로 돌아갔습니다.

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

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

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    var cnt = 1
    while (true) {
        val n = br.readLine().toInt()

        if (n == 0) break

        val array = Array(n) { br.readLine().split(" ").map { it.toInt() }.toIntArray() }

        val weight = bfs(0 to 1, n-1 to 1, array)

        bw.write("${cnt++}. $weight")
        bw.newLine()
    }

    br.close()
    bw.close()
}

fun bfs(
    start: Pair<Int, Int>,
    end: Pair<Int, Int>,
    array: Array<IntArray>
): Int {
    var answer = Int.MAX_VALUE
    val queue = LinkedList<Node>()
    val visited = mutableSetOf<Pair<Int, Int>>()

    queue.add(Node(start.first, start.second, array[start.first][start.second]))
    visited.add(start)

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

        if (cur.x to cur.y == end) {
            answer = min(answer, cur.weight)
        }

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

            if (nx < 0 || ny < 0 || nx > array.lastIndex || ny > array[0].lastIndex) {
                continue
            }

            visited.add(nx to ny)
            queue.add(Node(nx, ny, array[nx][ny] + cur.weight))
        }
    }
    return answer
}

class Node(
    val x: Int,
    val y: Int,
    val weight: Int,
)

2차 시도(DP)

2번째로 다익스트라를 사용할까 했지만 다익스트라의 조건(가장 최선의 결과를 따라 갔을때 최적의 결과가 나온다는 보장을 할 수 있어야한다)을 만족할 수 없다는 생각을 하게 되었고 이건 DP로 푸는 것이 맞다라는 결론에 도달하게 됩니다.

그래서 점화식을 세우고 문제를 해결하게되었습니다.

점화식은 다음과 같습니다.

$$$$\begin{align} &DP[i][j] = (i, j)위치에서 가지는 가장 적은 비용 \\ &DP[i][0] = min(DP[i-1][0], DP[i-1][1]) + array[i][0] \\ &DP[i][1] = min(DP[i-1][0], DP[i-1][1], DP[i-1][2], DP[i][0]) + array[i][1] \\ &DP[i][2] = min(DP[i-1][1], DP[i-1][2], DP[i][1]) + array[i][2] \end{align}$$

$$

점화식이 복잡하다고 생각이되지만 삼각 그래프의 특성으로 인해서 같은 행, 열일때와 아닐때는 구분해서 점화식에 고려를 해줘야하기 때문에 복잡할 수 밖에 없다고 생각이 됩니다.

결론 적으로 코드로 적으면 아래와 같습니다.

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    var cnt = 1

    while (true) {
        val n = br.readLine().toInt()

        if (n == 0) break

        val array = Array(n) { br.readLine().split(" ").map { it.toInt() }.toIntArray() }
        val dp = Array(n) { IntArray(3) { Int.MAX_VALUE } }

        // init
        dp[0][1] = array[0][1]
        dp[0][2] = dp[0][1] + array[0][2]

        for (i in 1 until n) {
            dp[i][0] = minOf(dp[i - 1][0], dp[i - 1][1]) + array[i][0]
            dp[i][1] = minOf(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i][0]) + array[i][1]
            dp[i][2] = minOf(dp[i - 1][1], dp[i - 1][2], dp[i][1]) + array[i][2]
        }

        bw.write("${cnt++}. ${dp[n - 1][1]}")
        bw.newLine()
    }

    br.close()
    bw.close()
}

여기서 주의할 점, 처음 row를 초기화를 잘 해야합니다.

        dp[0][1] = array[0][1]
        dp[0][2] = dp[0][1] + array[0][2]

(0, 1)에서 동작하기 때문에 (0, 1),(0, 2)에 대해서 초기화를 직접 해줘야하는 것을 고려해야합니다.