[백준] 삼각 그래프
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)에 대해서 초기화를 직접 해줘야하는 것을 고려해야합니다.