칼로리 계산(Back Tracking)

계곡의 돌다리는 5*5개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 모두 다르며 높이에 따라 건널 때마다 칼로리가 소비된다. 첫번째 지점에서 우리가 갈려고 하는 목표 위치의 돌까지 건널 때 가장 빠르게 도망가야 한다. 가장 빠르게 건널 수 있는 방법을 미리 알아두기 위해서 건너는 순서를 알아보자.

칼로리가 정해진 5*5 돌다리

3 7 2 1 9
5 8 3 9 2
5 3 1 2 3
5 4 3 2 1
1 7 5 2 4

출발 지점은 (0,0)이고 도착지는 (4,4)이다. 5*5배열로 표시한 값들은 돌다리를 건너는데 서로 다른 높이로 인하여 오르내리는데 필요한 칼로리를 표시한 것이다. 대각선의 돌다리는 사이가 멀기 때문에 바로 아래 돌다리나 오른쪽 돌다리로만 이동할 수 있다.

Explanation :

역시나 백트래킹 문제이다. 대각선과 좌측으로 이동할 수 없으므로, 최종 도착지에 이르는 동안 방문하는 돌다리는 모두 8개.
최종 도착지에 도착하되, 가능한 방법들을 모두 조사하여 각 방법마다 소모한 칼로리 수를 누적한다. 그리고 한번의 방법마다 누적된 칼로리 수를 기초로 하여 최소값의 칼로리를 구한다음 출력하면 된다.

재귀적으로 생각할 필요가 있다. 문제를 좁혀서 생각 해 보면, 처음 출발지의 칼로리는 '3'이다. 가능한 자리는 우측 돌다리인 '7'과 아래쪽 돌다리인 '5' 2개가 있다. 그중에 우측(7)을 선택한다고 치자.
그렇다 해도 문제는 달라지지 않는다. 또다시 이동가능한 돌다리는 우측과 아래쪽 두가지 뿐이다. 처음에 아래쪽인 '5'를 선택했어도 마찬가지 이다. 그러므로 우측을 방문하는 것은 x값을 증가시켜 재귀호출, 아래쪽을 방문하는 것은 y값을 증가시켜 재귀호출 하면 되는 것.

recursion(int x, int y)
{
recursion(x+1, y);
recursion(x, y+1);
}

이 되게 되는데 무한루프를 방지하기 위하여 조건을 달아준다.
5 by 5 배열이라 했으므로, 조건을 추가하면 아래와 같다.

if (x < 4)
recursion();
if (y < 4)
recursion();

하지만 이것으로 끝나지 않는다. 방문하면서 소모한 칼로리를 누적해야 하기 때문이다. 함수의 파라메터가 하나 더 추가된다. sum이라고 해 두자. 이동할 때마다 해당 칼로리 값을 누적해야 한다.

recursion(x+1, y, sum + 우측 칼로리 값)
recursion(x, y+1, sum + 아래쪽 칼로리 값)

그래서 x와 y값이 최종적으로 4값에 도달했을 경우 (x==4 && y==4)
최소값을 갱신한다.

if (x == 4 && y == 4)
if (sum < min) // 최소값 갱신
min = sum;

이것으로 충분할 것 같지만 그렇지 않다.
만약, 돌다리들을 방문하는 도중에 너무 많은 칼로리들을 소모하는 방법을 선택하는 경우라고 가정하자. 그리하여 최종 도착지점에 도착하기도 전에 누적된 칼로리 값이 현재 구해놓은 다른 방법의 최소 칼로리 값보다 커지는 경우라면 그 다음은 방문해 볼 필요가 없다.
물론 5 by 5 배열에서는 큰 속도의 성능향상이 없을수도 있다. 오히려 비교하는 시간이 더 많이 걸릴수도 있지만, 배열이 많이 커지는 경우에는 유용하다. N-Queen문제에서 이미 구현한 바 있다.

if (x < 4 && sum + 우측칼로리값 < min)
recursion();
if (y < 4 && sum + 아래쪽 칼로리값 < min)
recursion();

완성된 소스는 아래와 같다.


#include <stdio.h>
#include <limits.h> //use INT_MAX

int calorie[5][5] = {{3,7,2,1,9},{5,8,3,9,2},{5,3,1,2,3},{5,4,3,2,1},{1,7,5,2,4}};
int g_min_calorie = INT_MAX; //임의의 큰 값으로 초기화

void find(int y, int x, int sum)
{
// printf("%d ", calorie[y][x]); 중간확인을 위해 찍어봄(주석처리)

if (x == 4 && y == 4)
{
//한번의 순회후 누적된 칼로리들의 최소값을 구한다
if (sum < g_min_calorie)
g_min_calorie = sum;
}

else
{
//우측으로 이동가능 하고, 현재까지의 누적 칼로리보다 작으면 이동
if (x < 4 && g_min_calorie > sum + calorie[y][x+1])
find(y, x+1, sum + calorie[y][x+1]);

//하단으로 이동가능 하고, 현재까지의 누적 칼로리보다 작으면 이동
if (y < 4 && g_min_calorie > sum + calorie[y+1][x])
find(y+1, x, sum + calorie[y+1][x]);
}
}

void print(void)
{
printf("\nMin Calories = %d \n", g_min_calorie);
}

void main(void)
{
//0,0부터 시작, sum값은 시작값으로 초기화
find(0,0,calorie[0][0]);

//인쇄
print();
}