[BOJ][C++] 백준 4883번: 삼각 그래프

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은 최소 비용이다.

 

풀이

dp[i][j] = i행 j열까지 가는 최소 비용

 

비용이!! 음수가 될 수 있다!!! 는 점을!! 유의하자!!!!! 아악!!

 

dp의 첫번째 줄(0행, dp[0][n])의 초깃값을 잘 정해야한다

graph[0][0] 은 지나갈 일이 없으므로 그냥 가장 큰 거 넣어줬다

graph[0][2] 를 지나가려면 무조건 graph[0][1]을 지나가야 유효하므로 두 수의 합을 넣어둔다

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1000;

int n, ans;

int solution(vector<vector<int>>&graph) {
    vector<vector<int>>dp(n, vector<int>(3));
    dp[0][0] = INF;
    dp[0][1] = graph[0][1];
    dp[0][2] = graph[0][1] + graph[0][2];
    
    for(int i=1; i<n; i++) {
        dp[i][0] = min({dp[i-1][0], dp[i-1][1]}) + graph[i][0];
        dp[i][1] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i][0]}) + graph[i][1];
        dp[i][2] = min({dp[i-1][1], dp[i-1][2], dp[i][1]}) + graph[i][2];
    }
    
    return dp[n-1][1];
}

int main() {
	for(int i=1; true; i++) {
	   cin >> n;
	   
	   if(n==0) {
	       break;
	   }
	   
	   // 입력
	   vector<vector<int>>graph(n, vector<int>(3));
	    for(int i=0; i<n; i++) {
	        for(int j=0; j<3; j++) {
	            cin >> graph[i][j];
	        }
	    }
	    
	    // 풀이
	    ans = solution(graph);
	   
	    // 출력
	    cout << i << ". " << ans << "\n";
	}
    
    return 0;
}