문제

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

삼각 그래프는 사이클이 없는 그래프로 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값)

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 100005;

	int N;
	int arr[MAX][3];
	// dp[i][j] : 출발하여 i번째 행, j번째 열 까지 가는 최소 비용
	int dp[MAX][3];

	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int testcase = 1;
	while (cin >> N) {
	if (N == 0) break;

	for (int i = 0; i < N; ++i) {
	for (int j = 0; j < 3; ++j) {
	cin >> arr[i][j];
	dp[i][j] = arr[i][j]; // 기본적으로 자기 자신
	}
	}
	dp[0][2] += dp[0][1];
	dp[0][0] = 1987654321; // dp[0][0] 에서 내려갈 수는 없다.

	for (int col = 1; col < N; ++col) {
	// 바로 전 row의 0, 1 에서 옴
	dp[col][0] += min(dp[col - 1][0], dp[col - 1][1]);
	// 바로 전 row의 0,1,2 or 같은 row의 0 에서 옴
	dp[col][1] += min({ dp[col - 1][0], dp[col - 1][1], dp[col - 1][2], dp[col][0] });
	// 바로 전 row의 1, 2 or 같은 row의 1 에서 옴
	dp[col][2] += min({ dp[col - 1][1], dp[col - 1][2], dp[col][1] });
	}

	cout << testcase++ << ". " << dp[N - 1][1] << '\n';
	}

	return 0;
	}

view raw BOJ 4883.cpp hosted with ❤ by GitHub