3차원 배열 cube[length][breadth][height] 형태로 표현할 수 있는 큐브가 주어졌을 때, 큐브를 순회하며 얻을 수 있는 최소 합 경로(minimum sum path)를 계산하고 그 결과를 출력하는 것이 이 문제의 목표입니다.
입출력 예시
입력 − int cube[length][breadth][height] = { { {2, 4, 1}, {3, 4, 5}, {9, 8, 7}}, { {5, 3, 2}, {7, 6, 5}, {8, 7, 6}}, { {3, 2, 1}, {4, 3, 2}, {5, 4, 3}}}
출력 − 3차원 배열의 최소 합 경로: 15
설명 − 길이, 너비, 높이를 가진 큐브가 주어졌습니다. 3차원 배열에서 최소 합 경로를 계산하면 시작점부터 2 + 4 + 1 + 3 + 5, 즉 15가 됩니다.
입력 − int cube[length][breadth][height] = { { {1, 2}, {7, 8}}, { {3, 5}, {9, 16}}}
출력 − 3차원 배열의 최소 합 경로: 24
설명 − 마찬가지로 큐브를 따라 이동하며 최소 합 경로를 계산하면 1 + 2 + 5 + 16, 즉 24가 됩니다.
적용된 알고리즘 접근 방식
정수 값으로 구성된 3차원 배열(큐브)을 입력받고, 해당 데이터를 Minimum_SubPath(cube) 함수에 전달합니다.
Minimum_SubPath(cube) 함수 내부에서 다음을 수행합니다.
큐브와 같은 크기의 배열 arr을 생성하고, arr[0][0][0]을 cube[0][0][0]으로 초기화합니다.
i를 1부터 큐브의 길이까지 반복하며 arr[i][0][0]을 arr[i-1][0][0] + cube[i][0][0]으로 설정합니다.
j를 1부터 큐브의 너비까지 반복하며 arr[0][j][0]을 arr[0][j-1][0] + cube[0][j][0]으로 설정합니다.
k를 1부터 큐브의 높이까지 반복하며 arr[0][0][k]를 arr[0][0][k-1] + cube[0][0][k]로 설정합니다.
i를 1부터 길이까지, j를 1부터 너비까지 이중 반복하며 min_val을 Minimum(arr[i-1][j][0], arr[i][j-1][0], INT_MAX)로 구한 뒤, arr[i][j][0]을 min_val + cube[i][j][0]으로 설정합니다.
i를 1부터 길이까지, k를 1부터 높이까지 이중 반복하며 min_val을 Minimum(arr[i-1][0][k], arr[i][0][k-1], INT_MAX)로 구한 뒤, arr[i][0][k]를 min_val + cube[i][0][k]로 설정합니다.
k를 1부터 높이까지, j를 1부터 너비까지 이중 반복하며 min_val을 Minimum(arr[0][j][k-1], arr[0][j-1][k], INT_MAX)로 구한 뒤, arr[0][j][k]를 min_val + cube[0][j][k]로 설정합니다.
i, j, k를 각각 1부터 길이, 너비, 높이까지 삼중 반복하며 min_val을 Minimum(arr[i-1][j][k], arr[i][j-1][k], arr[i][j][k-1])로 구한 뒤, arr[i][j][k]를 min_val + cube[i][j][k]로 설정합니다.
최종적으로 arr[length-1][breadth-1][height-1] 값을 반환합니다.
Minimum(int a, int b, int c) 함수 내부에서는 다음을 수행합니다.
a가 b보다 작고 c보다도 작으면 a를 반환합니다.
그렇지 않고 b가 c보다 작으면 b를 반환합니다.
그 외의 경우에는 c를 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
#define length 3
#define breadth 3
#define height 3
int Minimum(int a, int b, int c){
if(a < b){
if(a < c){
return a;
}
else{
return c;
}
}
else if(b < c){
return b;
}
else{
return c;
}
}
int Minimum_SubPath(int cube[][breadth][height]){
int i, j, k;
int arr[length][breadth][height];
arr[0][0][0] = cube[0][0][0];
for(i = 1; i < length; i++){
arr[i][0][0] = arr[i-1][0][0] + cube[i][0][0];
}
for(j = 1; j < breadth; j++){
arr[0][j][0] = arr[0][j-1][0] + cube[0][j][0];
}
for(k = 1; k < height; k++){
arr[0][0][k] = arr[0][0][k-1] + cube[0][0][k];
}
for(i = 1; i < length; i++){
for(j = 1; j < breadth; j++){
int min_val = Minimum(arr[i-1][j][0], arr[i][j-1][0], INT_MAX);
arr[i][j][0] = min_val + cube[i][j][0];
}
}
for(i = 1; i < length; i++){
for(k = 1; k < height; k++){
int min_val = Minimum(arr[i-1][0][k], arr[i][0][k-1], INT_MAX);
arr[i][0][k] = min_val + cube[i][0][k];
}
}
for(k = 1; k < height; k++){
for(j = 1; j < breadth; j++){
int min_val = Minimum(arr[0][j][k-1], arr[0][j-1][k], INT_MAX);
arr[0][j][k] = min_val + cube[0][j][k];
}
}
for(i = 1; i < length; i++){
for(j = 1; j < breadth; j++){
for(k = 1; k < height; k++){
int min_val = Minimum(arr[i-1][j][k], arr[i][j-1][k], arr[i][j][k-1]);
arr[i][j][k] = min_val + cube[i][j][k];
}
}
}
return arr[length-1][breadth-1][height-1];
}
int main(){
int cube[length][breadth][height] = { { {2, 4, 1}, {3, 4, 5}, {9, 8, 7}},
{ {5, 3, 2}, {7, 6, 5}, {8, 7, 6}},
{ {3, 2, 1}, {4, 3, 2}, {5, 4, 3}}};
cout<<"Minimum Sum Path In 3-D Array are: "<<Minimum_SubPath(cube);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Minimum Sum Path In 3-D Array are: 15
복잡도 분석
이 알고리즘은 동적 계획법(DP)을 활용하여 세 축 방향(길이, 너비, 높이)으로만 이동 가능한 경로 중 누적 합이 가장 작은 경로를 찾습니다. 시간 복잡도는 O(length × breadth × height), 공간 복잡도 역시 큐브와 같은 크기의 DP 테이블을 사용하므로 O(length × breadth × height)입니다.