[알고리즘] 동적프로그래밍 - 길찾기

동적 프로그래밍(Dynamic Programming)

동적프로그래밍, 동적 계획법이라고도 표현한다.

동적 프로그래밍은 재귀의 중복으로 계산시간이 오래걸릴 때 

메모이제이션을 대체 할 다른 방법이다.

동적 프로그래밍을 잘 사용하면 재귀보다 크게 성능을 향상 시킬 수 있다.

따라서 소프트웨어 직군의 알고리즘 시험에 종종 출제되니 꼭 짚고 넘어가도록 하자

1. 재귀로 구현한 길찾기

동적프로그래밍의 대표적인 문제는 길찾기이다.

고등학교때 한번씩 다 풀어본 문제일 것이다.

위와같은 경로가 있을때 A에서 B까지 도달할 수 있는 최단 경로는 얼마일까?

답은 다음과 같다.

A에서 부터 시작하여 (i,0), (0,j)를 1이라고 하면

다음 경로는 아래위의 합과 같다.

이와같이 더해나가면 끝에서 최단 경로를 구할 수 있다.

이를 점화식으로 나타내면 다음과 같다.

1. map[i][j] = 0 이면 path(i,j)는 0이다

2. map[i][j] =  1일때,

1) i=0, j=0 이면, path(i, j)=1

2) i>0, j=0 이면, path(i, j)=path(i-1, j)

3) i=0. j>0  이면, path(i, j) = path(i, j-1)

4) i>0, j>0 이면, path(i, j) = path(i-1, j)+path(i, j-1)

map은 크게 2가지, 갈수있는 경로와 갈수 없는 경로로 나뉜다.

갈수 있는 경로일때는 다시 4가지의 세부사항으로 나뉜다.

1) 출발 지점에 대한 값

2) 첫번째 행에 대한 값

3) 첫번째 열에 대한 값

4) 1에서 3까지를 제외한 나머지 값

 

#include<stdio.h>
 
#define capa 100
long cal_path(int n, int m);
 
int map[capa][capa];
 
 
int main(){
    int n,m,i,j;
    
    scanf("%d %d", &n, &m);
    
    for(i=0; i<n; i++){
        for(j=0; j<m; j++){
            scanf("%d", &map[i][j]);
        }
    }
    
    printf("%ld", cal_path(m-1,n-1));
    
    return 0;
}
long cal_path(int m, int n){
    
    if(map[0][0]==0)
        return 0;
    if(m==0 && n==0)
        return 1;
    
    return ((m>0) ? cal_path(m-1,n) : 0 )+((n>0) ? cal_path(m,n-1) : 0);                                    
}
 

이를 코드로 나타내면 위와 같이 작성할 수 있다.

반복문을 통하여 일정한 크기의 배열을 받고

cal_path 함수를 통해 최단경로를 계산한다.

if는 2-1,2,3조건에 대한 구현이며 재귀조건을 통하여 

다른 지점에 대한 경로 계산이 가능하다

그림으로 나타내면 다음과 같다.

(M,N)을 출발하여 return문의 조건에 진입 하면서 다른 경로의 수들을 계산하게 된다.

즉, 위에서 아래로 흐르며(Top down) 재귀를 통해 계산이 이루어 진다.

2. 동적 프로그래밍으로 구현한 길찾기

다음은 동적 프로그래밍으로 구현한 길찾기이다

앞에서 설명한 점화식을, 이번에는 아래서부터 채워나간다.

소스코드는 아래와 같다.

 

#include<stdio.h>
 
#define capa 100
void cal_path(int n, int m);
 
int map[capa][capa];
int path[capa][capa];
 
int main(){
    int n,m,i,j;
    
    scanf("%d %d", &m, &n);
    
    for(i=0; i<m; i++){
        for(j=0; j<n; j++){
            scanf("%d", &map[i][j]);
        }
    }
    
    cal_path(m, n);
    
    return 0;
}
 
void cal_path(int m, int n){
    
    int i, j;
    
    path[0][0] = map[0][0];
    for(i = 1; i < m; i++){
        if(map[i][0]==0)
            path[i][0]=0;
        else
            path[i][0]= path[i-1][0];
    }
    for(j=1; j<n; j++){
        if(map[0][j]==0)
            path[0][j]=0;
        else
            path[0][j]=path[0][j-1];
    }
    for(i=1; i<m; i++){
        for(j=1; j<m; j++){
            if(map[i][j]==0)
                path[i][j]=0;
            else{
                path[i][j]= path[i-1][j]+path[i][j-1];                                                      
            }
        }
    }
    printf("%d\n", path[m-1][n-1]);
}
 

다음의 코드는 지도를 입력받는 map과 경로를 계산하는 path, 

두개의 이차원 배열을 이용하여 계산하는 코드이다.

재귀호출로 인해 딜레이가 생긴다면 다음의 코드를 사용할 수 있다.

동적프로그래밍은 재귀와 다르게 상향식(Bottom-up)으로 문제를 해결해 나간다.