7-3. 동적 계획법 예제 문제 - #2. TRIANGLE_PATH(삼각형 위의 최대경로)

1. TRIANGLEPATH

ex) 5행 TRIANGLEPATH 문제

6

1 2

3 7 4

9 4 1 7

2 7 5 9 4

맨 위 꼭지점부터 시작하여 한 단계씩 아래로 내려가며 경로를 선택한다

이 때 바로 아래의 숫자 혹은 아래 오른쪽의 숫자로만 이동이 가능하다.

맨 아래 줄까지 내려가면 경로가 완성되고 선택한 경로의 숫자를 더하여 최종 결과를 얻는다.

이 문제의 목표는 숫자 합이 최대가 되는 값을 찾는 것이다.

 

2. 코드 분석

#include <iostream>
#include <windows.h>
#include <vector>
using namespace std;

// 6
// 1 2
// 3 7 4
// 9 4 1 7
// 2 7 5 9 4

int N = 5;
vector<vector<int>> board; // N x N size
vector<vector<int>> cache;
vector<vector<int>> nextX;
// 문제가 요구하는 정답을 반환한다

int path(int y, int x)	// 경로의 합을 반환
{
	// 하단 혹은 우측 하단으로 이동, 재귀적으로 호출
	// 1. 예외 사항 파악
	if (y == N)
		return 0;

	// 2. 캐시 메모리 확인
	int& ret = cache[y][x];
	if (ret != -1)
		return ret;

	// 3. 정답 찾기 - 아래, 아래 우측으로 이동하며 합이 최대가 되는 경로
	//board[y][x] + path(y + 1, x);
	//board[y][x] + path(y + 1, x + 1);
	
	// 경로 기록
	{
		int nextBot = path(y + 1, x);
		int nextBotRight = path(y + 1, x + 1);
		if (nextBot > nextBotRight)
			nextX[y][x] = x;
		else
			nextX[y][x] = x + 1;
	}
	return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}


int main()
{
	board = vector<vector<int>>
	{
		{6},
		{1, 2},
		{3, 7 ,4 },
		{9, 4, 1, 7},
		{2, 7, 5, 9, 4}
	};
	cache = vector<vector<int>>(N, vector<int>(N, -1));
	nextX = vector<vector<int>>(N, vector<int>(N));



	int ret = path(0, 0);
	cout << ret << "\n";

	// 경로 만들기
	int y = 0;
	int x = 0;

	while (y < N)
	{
		cout << board[y][x] << " -> ";

		x = nextX[y][x];
		y++;
	}
}

 

(1) 보드 만들기

// 6
// 1 2
// 3 7 4
// 9 4 1 7
// 2 7 5 9 4

int N = 5;
vector<vector<int>> board; // N x N size
vector<vector<int>> cache;
vector<vector<int>> nextX;

N by N 사이즈를 가지는 보드를 만든다.

중복 계산을 회피하기 위해 캐시와 다음 경로를 추적하는 nextX를 이중 배열로 만든다.

 

(2) 문제 해결

int path(int y, int x)	// 경로의 합을 반환
{
	// 하단 혹은 우측 하단으로 이동, 재귀적으로 호출
	// 1. 예외 사항 파악
	if (y == N)
		return 0;

	// 2. 캐시 메모리 확인
	int& ret = cache[y][x];
	if (ret != -1)
		return ret;

	// 3. 정답 찾기 - 아래, 아래 우측으로 이동하며 합이 최대가 되는 경로
	//board[y][x] + path(y + 1, x);
	//board[y][x] + path(y + 1, x + 1);

	return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}

문제를 해결하기에 앞서 문제가 원하는 정답이 무엇인지 파악한다.

위에서는 최대 경로의 합을 구하기를 원한다. 따라서 int형의 함수로 선언한다.

 

- 예외 사항 파악하기

삼각형을 따라가다가 최하단에 도달하면(N - 1) 코드가 중지되어야 한다. 따라서 y가 최하단을 넘어가면 0을 리턴하도록 한다.

 

- 캐시 메모리 확인하기

이미 도출한 정답이 있는지 확인한다.

캐시 메모리는 아래의 main 함수에서 N by N 사이즈와 기본값 -1로 초기화되어 있기 때문에,

이미 답을 구한 상태라면(-1이 아닌 값을 이미 가지고 있다면) 그 값을 반환하기로 한다.

 

- 정답 찾기

보드의 지금 좌표의 값에 다음 경로 중, 하단으로 갔을 때와 우하단으로 갔을 때 더 큰 값을 더하여 반환한다.

 

(3) main 함수

int main()
{
	board = vector<vector<int>>
	{
		{6},
		{1, 2},
		{3, 7 ,4 },
		{9, 4, 1, 7},
		{2, 7, 5, 9, 4}
	};
	cache = vector<vector<int>>(N, vector<int>(N, -1));
	nextX = vector<vector<int>>(N, vector<int>(N));

	int ret = path(0, 0);
	cout << ret << "\n";
}

이중 배열로 구성된 보드를 주어진 문제의 값으로 대입시켜준다.

캐시는 N by N 사이즈의 -1 값으로 초기화 되어 있다.

이어서 경로를 추적하기 위한 nextX를 N by N 이중 배열로 초기화한다.

 

(4) 경로 추적하기

	{
		int nextBot = path(y + 1, x);
		int nextBotRight = path(y + 1, x + 1);
		if (nextBot > nextBotRight)
			nextX[y][x] = x;
		else
			nextX[y][x] = x + 1;
	}

path 함수의 return 이전에 추가한다.

하단으로 내려가는 경로와 우하단으로 내려가는 경로를 저장한다.

두 값을 비교해 더 큰 값을 nextX에 저장해서 관리한다.

 

	int y = 0;
	int x = 0;

	while (y < N)
	{
		cout << board[y][x] << " -> ";

		x = nextX[y][x];
		y++;
	}

main 함수의 마지막 부분에 추가한다.

보드의 좌표를 추적할 y와 x를 (0, 0)으로 초기화한다.

y가 보드의 크기보다 작을 동안 반복문을 돌려주고 x에 nextX를 넣어 값을 출력한다.