문제

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

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

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

문제풀이

사용한 알고리즘 : DP

'dp[i][j] : 출발해서 i행, j열 까지 가는 최소 비용' 으로 설정하였습니다.

이에 따라 구하고자 하는 값은 dp[N-1][1] 입니다. (0-indexed)

출발은 첫째 행, 두번째 열에서만 가능함을 생각합니다.

( 0-indexed 으로 생각하고, 각 노드의 비용은 arr 배열에 저장하였다고 생각하겠습니다. )

기본적으로 모든 노드의 dp 값에는 해당 노드의 비용이 포함됩니다.

출발은 (0, 1) 에서만 가능하므로

dp[0][1] = arr[0][1] ,

dp[0][2] = arr[0][1] + arr[0][2] 입니다.

출발지 (0,1) 에서 (0,0) 은 갈 수 없으니

dp[0][0] = 매우 큰 수 로 설정하였습니다.

이후 두번째 행부터는 다음과 같이 dp 값이 최신화 됩니다.

1. dp[i][0] = arr[i][0] + min(바로 위 행의 0, 1번째 dp값)

2. dp[i][1] = arr[i][1] + min(바로 위 행의 0, 1, 2번째 혹은 같은 행의 0번째 dp값)

3. dp[i][2] = arr[i][2] + min(바로 위 행의 1, 2번째 혹은 같은 행의 1번째 dp값)