[11048번] 이동 하기 (Recursive, Dynamic Programming)

문제 출처 : 

https://www.acmicpc.net/problem/11048

알고리즘 분석 :

Recursive(재귀), Dynamic Programming 두가지 방법이 존재하는 문제이다.

Recursive를 이용하면 조금 더 코딩이 수월하지만, 테스트 규모가 커질수록 재귀를 통한 시간 복잡도가 상당히 증가함을 알 수 있다.

따라서 이 문제는 Dynamic Programming으로 풀어야 한다.

소스 코드 : 

< Recursive를 통한 해석 > (시간 복잡도가 높은 코드이다.)

#include <stdio.h>
 
int map[1001][1001] = { -1, };
int max = 0;
 
void recursive(int x, int y, int tmp)
{
    tmp = tmp + map[y][x];
 
    if (tmp >= max)
        max = tmp;
 
    if (map[y][x + 1] != -1)
        recursive(x + 1, y, tmp);
 
    if (map[y + 1][x] != -1)
        recursive(x, y + 1, tmp);
 
    if (map[y + 1][x + 1] != -1)
        recursive(x + 1, y + 1, tmp);
}
 
int main()
{
    int x, y;
    int i, j, value;
    int sum = 0, tmp = 0;
 
    scanf("%d %d", &y, &x);
 
    for (i = 0; i < y + 1; i++)
    {
        for (j = 0; j < x + 1; j++)
        {
            map[i][j] = -1;
        }
    }
 
    for (i = 0; i < y; i++)
    {
        for (j = 0; j < x; j++)
        {
            scanf("%d", &value);
            map[i][j] = value;
        }
    }
 
 
 
    recursive(0, 0, tmp);
 
    printf("%d", max);
 
    return 0;
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>

< Dynamic Programming을 통한 해석 >

#include <stdio.h>
 
int map[1002][1002];
 
int getBestValue(int y, int x)
{
    int tmp[4] = { 0,0,0,0 }, max, k;
 
    // 1,1의 값은 비교 없이 출발점이니 리턴해준다.
    if (x == 1 && y == 1)
        return map[1][1];
 
    // 현재 값과 왼쪽 값을 더한 것을 tmp[1]에 넣는다.
    if (map[y][x - 1] != -1)
        tmp[1] = map[y][x] + map[y][x - 1];
 
    // 현재 값과 위쪽 값을 더한 것을 tmp[2]에 넣는다.
    if (map[y - 1][x] != -1)
        tmp[2] = map[y][x] + map[y - 1][x];
 
    // 현재 값과 왼쪽 위의 값을 더한 것을 tmp[3]에 넣는다.
    if (map[y - 1][x - 1] != -1)
        tmp[3] = map[y][x] + map[y - 1][x - 1];
 
    // 그중 가장 큰 값을 max에 저장시킨다.
    max = tmp[1];
    for (k = 2; k <= 3; k++)
    {
        if (tmp[k] > max)
            max = tmp[k];
    }
 
    return max;
 
}
 
int main()
{
    int x, y;
    int i, j, value;
    int sum = 0, tmp = 0;
 
    scanf("%d %d", &y, &x);
 
 
    // map 0으로 초기화
    for (i = 0; i <= y + 1; i++)
    {
        for (j = 0; j <= x + 1; j++)
        {
            map[i][j] = 0;
        }
    }
 
 
    // 벽 생성 (-1은 벽으로 간주한다.)
    for (i = 0; i <= y + 1; i++)
        map[i][0] = -1;
 
    for (i = 0; i <= y + 1; i++)
        map[i][x + 1] = -1;
 
    for (j = 0; j <= x + 1; j++)
        map[0][j] = -1;
 
    for (j = 0; j <= x + 1; j++)
        map[y + 1][j] = -1;
 
    for (i = 1; i <= y; i++)
    {
        for (j = 1; j <= x; j++)
        {
            scanf("%d", &value);
            map[i][j] = value;
        }
    }
    /*
    // map 출력
    for (i = 0; i <= y + 1; i++)
    {
    for (j = 0; j <= x + 1; j++)
    {
    printf("%d ", map[i][j]);
    }
    printf("\n");
    }
    */
 
    for (i = 1; i <= y; i++)
    {
        for (j = 1; j <= x; j++)
        {
            // return 받은 값을 map에 갱신한다.
            map[i][j] = getBestValue(i, j);
        }
    }
 
    /*
    // Dynamic Programming 결과 map 출력
    for (i = 0; i <= y + 1; i++)
    {
    for (j = 0; j <= x + 1; j++)
    {
    printf("%d ", map[i][j]);
    }
    printf("\n");
    }
    */
    printf("%d", map[y][x]);
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>