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

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 문제. 비용이 음수가 주어질 수 있다는 것에 주의해야 한다.

정점까지 가는 최소 비용을 저장하는 2차원 배열을 dp라고 하자. dp[i][0]은 i번째 줄 왼쪽 정점, dp[i][1]은 i번째 줄 가운데 정점, dp[i][2]는 i번째 줄 오른쪽 정점까지의 최소 비용을 의미한다.

i번째 줄 왼쪽 정점은 i-1번째 줄 왼쪽 또는 가운데에서부터 올 수 있다. 따라서 i번째 줄 왼쪽 칸까지 가는데 필요한 비용은 dp[i-1][0]+입력 배열 arr[i][0] 혹은 dp[i-1][1]+입력 배열 arr[i-1][0]이다. 그러므로 i번째 줄 왼쪽 칸까지 가는데 필요한 최소 비용은 min(dp[i-1][0], dp[i-1][1])+arr[i][0]이 된다.

i번째 줄 가운데 정점은 i-1번째 줄 왼쪽 정점, 가운데 정점, 오른쪽 정점, i번째 줄 왼쪽 정점으로부터 올 수 있다. 따라서 해당 정점까지 가는데 필요한 최소 비용은 min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i][0])+arr[i][1]이 된다.

i번째 줄 오른쪽 정점은 i-1번째 줄 가운데 정점, 오른쪽 정점, i번째 줄 가운데 정점으로부터 올 수 있다. 따라서 해당 정점까지 가는데 필요한 최소 비용은 min(dp[i-1][1], dp[i-1][2], dp[i][1])+arr[i][2]이 된다.

 

출발점은 항상 첫번째 줄 가운데 정점에서 시작하므로 두번째 줄에서 최소 비용이 이전 줄의 왼쪽 정점이나 오른쪽 정점에서 오는 상황을 만들어서는 안된다. 해당 상황을 방지하기 위해 dp[0][0]을 MAX로 초기화한다. 또한 오른쪽 정점은 arr[0][1]+arr[0][2]로 초기화함으로써, 오른쪽 정점이 0보다 클 경우에는 두번째 줄에서의 최소 비용이 이전 줄의 오른쪽 정점으로부터 오는 상황을 막고, 0보다 작을 경우에는 가운데 정점 -> 오른쪽 정점으로 이동하며 비용을 줄일 수 있게 한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#define MAX 987654321
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	int testCase = 1;
	while (true)
	{
		cin >> N;
		if (N == 0)
		{
			break;
		}
		int** arr = new int* [N];
		long long** dp = new long long* [N];
		for (int i = 0; i < N; i++)
		{
			arr[i] = new int[3];
			dp[i] = new long long[3];
			for (int j = 0; j < 3; j++)
			{
				cin >> arr[i][j];
				dp[i][j] = 0;
			}
		}
		dp[0][0] = MAX;
		dp[0][1] = arr[0][1];
		dp[0][2] = arr[0][1] + arr[0][2];
		for (int i = 1; i < N; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				if (j == 0)
				{
					dp[i][j] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][j];
				}
				else if (j == 1)
				{
					dp[i][j] = min({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i][0] }) + arr[i][j];
				}
				else
				{
					dp[i][j] = min({ dp[i - 1][1], dp[i - 1][2], dp[i][1] }) + arr[i][j];
				}
			}
		}
		cout <<testCase<<". " << dp[N - 1][1] << "\n";
		testCase++;
	}
	return 0;
}