[알고리즘/C++] 동적계획법 - 최대 값의 경로 찾기

2차원의 공간이 주어지고 각 인덱스의 공간마다 특정 값(Value)가 주어진다. 

 

가장 상단 왼쪽의 격자부터 가장 하단 오른쪽의 격자로 이동하면서 경로 상의 값이 총합이 최대가 되도록 

 

하는 알고리즘을 동적 계획법으로 풀어보자. 

 

이동 조건은 오른쪽 혹은 아래 방향으로만 움직인다는 것이다.

 

1	2	1	2	0
1	3	4	5	6
1	2	3	5	1

 

위의 예시에서는 

1	2	1	2	0
1	3	4	5	6
1	2	3	5	1

위의 경로로 이동하는 것이 최대값을 가진다. 

int maxSumRoute(vector<vi> arr) {
	vector<vi> sum(arr.size(), vi(arr[0].size(), 0));
	for (int i = 0; i < arr.size(); i++) {
		for (int j = 0; j < arr[0].size(); j++) {
			if (i == 0 && j == 0) {
				sum[0][0] = arr[0][0];
				continue;
			}
			if (j == 0) {
				sum[i][j] = sum[i - 1][j] + arr[i][j];
				continue;
			}
			if (i == 0) {
				sum[i][j] = sum[i][j - 1] + arr[i][j];
				continue;
			}
			sum[i][j] = max(sum[i-1][j], sum[i][j-1]) + arr[i][j];
		}
	}
	return sum[arr.size()-1][arr[0].size()-1];
}

전체 코드는 위와 같다. 

 

	vector<vi> sum(arr.size(), vi(arr[0].size(), 0));

먼저 각 경로의 값 총합을 담는 배열을 동일 형상으로 선언한다. 

 

	for (int i = 0; i < arr.size(); i++) {
		for (int j = 0; j < arr[0].size(); j++)

경로 상의 각 격자들을 순회하면서 

 

			if (i == 0 && j == 0) {
				sum[0][0] = arr[0][0];
				continue;
			}

가장 첫번째 격자에서는 비교대상이 없으므로 첫번째 인덱스를 그대로 복사하고 continue한다.

			if (j == 0) {
				sum[i][j] = sum[i - 1][j] + arr[i][j];
				continue;
			}

만약 해당 격자가 가장 왼쪽의 격자라면 이동할 수 있었던 경로가 바로 위 밖에 없으므로 위의 값에 해당 격자의 value를 

 

더해준다. 

			if (i == 0) {
				sum[i][j] = sum[i][j - 1] + arr[i][j];
				continue;
			}

반대로 가장 상단의 격자를 만났다면, 이동할 수 있었던 방향이 왼쪽으로부터 올 수 밖에 없었으므로 

 

왼쪽의 값에서 현재 격자의 value를 더해준다. 

 

sum[i][j] = max(sum[i-1][j], sum[i][j-1]) + arr[i][j];

그리고 동적 프로그래밍에서 가장 핵심이 되는 코드이다. 

 

continue를 만나지 않고 그대로 내려왔으므로 비교 대상이 위에서 왔냐, 왼쪽에서 왔냐인데 

 

그 두가지의 값을 비교해서 더 큰 값을 현재 격자의 value에 더해준다. 

return sum[arr.size()-1][arr[0].size()-1];

모든 순회가 종료되었으면 가장 하단 우측의 격자가 담은 sum 값을 반환한다. 

	vector<vi> arr = { {3, 7, 9, 2, 7}, {9, 8, 3, 5, 5}, {1, 7, 9, 8, 5}, {3, 8, 6, 4, 10}, {6, 3, 9, 7, 8} };
	cout << maxSumRoute(arr);

결과 값은 67이다.