[백준 4883번] 삼각 그래프 (C++)

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

4883번: 삼각 그래프

---

삼각 그래프 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 

⚠️ 단, 비용이 음수가 될 수 있다는 것을 주의해야합니다.

삼각 그래프 예시

먼저, 테이블 d[i][j]는 i행 j열로 이동하는 최소 비용으로 정의했습니다.

따라서, 초기값은 아래와 같습니다.

d[0][0] = INT_MAX, d[0][1] = graph[0][1], d[0][2] = graph[0][1] + graph[0][2]

d[0][0]은 접근할 수 없으므로 INT_MAX로 정의하였습니다.

 

또한, d[i][0]으로 이동할 수 있는 정점은 d[i - 1][0]과 d[i - 1][1]이므로, d[i][0]은 아래와 같이 정의할 수 있습니다.

(단, graph[i][j]는 i번째 행, j번째 열의 정점의 비용)

d[i][0] = min({d[i - 1][0], d[i - 1][1]}) + graph[i][0];

마찬가지로, 아래와 같이 d[i][1]과 d[i][2]를 정의할 수 있습니다.

d[i][1] = min({d[i - 1][0], d[i - 1][1], d[i - 1][2], d[i][0]}) + graph[i][1];
d[i][2] = min({d[i - 1][1], d[i - 1][2], d[i][1]}) + graph[i][2];

 

 

아래는 Bottom-Up 방식의 다이나믹 프로그래밍 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int graph[100010][3], d[100010][3]; // d[i][j]는 i행 j열로 이동하는 최소 비용
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(true){
        int n; cin >> n;
        if(!n) break;
        fill(&graph[0][0], &graph[100009][3], 0);

        for(int i = 0; i < n; i++)
            for(int j = 0; j < 3; j++)
                cin >> graph[i][j]; // 삼각 그래프 입력 받음

        // 초기값 지정
        d[0][0] = INT_MAX, d[0][1] = graph[0][1], d[0][2] = graph[0][1] + graph[0][2];
        
        // 테이블 채우기
        for(int i = 1; i < n; i++){
            d[i][0] = min({d[i - 1][0], d[i - 1][1]}) + graph[i][0];
            d[i][1] = min({d[i - 1][0], d[i - 1][1], d[i - 1][2], d[i][0]}) + graph[i][1];
            d[i][2] = min({d[i - 1][1], d[i - 1][2], d[i][1]}) + graph[i][2];
        }

        cout << t++ << ". " << d[n - 1][1] << "\n"; // 가장 하단의 가운데 정점까지의 최소 비용
    }
}