최단경로 찾기 - 재귀/메모제이션/동적 프로그래밍

길찾기 알고리즘

 

지금까지 동적프로그래밍이란 재귀 + 메모제이션 이라고 알고 있었다.

 

재귀의 단점을 발전시킨 것이 메모제이션이고 이는 Top-Down 방식으로 진행된다.

동적프로그래밍은 초기화 된 처음 값을 쌓아가는 방식으로 Bottom-Up 방식으로 진행된다.

둘다 아이디어는 같다. 부분 문제들의 값을 다른 메모리 배열에 저장하여 반복계산하지 않는다.

주로 선호되는 방식은 메모제이션이다.

 

점화식

# 점화식

if ( map[i][j] == 0 ) MEMO[i][j] = 0;

if ( map[i][j] == 1 ){

i==0, j==0 이면 MEMO[0][0] = 1;

i > 0, j==0 이면 MEMO[i][j] = MEMO[i-1][j];

i==0, j > 0 이면 MEMO[i][j] = MEMO[i][j-1];

i > 0, j > 0 이면 MEMO[i][j] = MEMO[i-1][j] + MEMO[i][j-1];

}

 

1. 기본 재귀 방식

public static int num_path(int m, int n){

        if (map[m][n] == 0) {
            return 0;
        }

        if(m == 0 && n == 0){
            return 1 ;
        }

        return ( (m > 0) ? num_path(m-1, n) : 0 ) + ( (n > 0) ? num_path(m, n-1) : 0 );
    }

 

2. 메모제이션 방식

public static int path_memo(int m, int n){



        if (map[m][n] == 0) { //불가능한 경로
            return memo[m][n] = 0;
        }

        if(m == 0 && n == 0) { //시작점
            return memo[m][n] = 1;
        }

        int a =0;
        int b=0;

        if(m != 0 && n != 0 && memo[m][n] != 0  ){
            return memo[m][n];
        }

        if(m>0){
            memo[m-1][n] = num_path(m-1, n);
            a =     memo[m-1][n];
        }else{
            a = 0;
        }

        if(n>0){
            memo[m][n-1] = num_path(m, n-1);
            b = num_path(m, n-1);
        }else{
            b = 0;
        }


        memo[m][n] = a+b;
        return memo[m][n];
    }

 

 

 

---

 

전체 소스

package org.kyhslam.algo;

public class d_20200611 {

    static int[][] map = {
            {1,1,1,1,1},
            {1,1,0,0,1},
            {1,1,1,1,1},
            {1,1,1,0,1},
            {0,0,1,1,1}
    };

    static int[][] memo = new int[5][5];





    public static int num_path(int m, int n){

        if (map[m][n] == 0) {
            return 0;
        }

        if(m == 0 && n == 0){
            return 1 ;
        }

        return ( (m > 0) ? num_path(m-1, n) : 0 ) + ( (n > 0) ? num_path(m, n-1) : 0 );
    }


    public static int path_memo(int m, int n){



        if (map[m][n] == 0) { //불가능한 경로
            return memo[m][n] = 0;
        }

        if(m == 0 && n == 0) { //시작점
            return memo[m][n] = 1;
        }

        int a =0;
        int b=0;

        if(m != 0 && n != 0 && memo[m][n] != 0  ){
            return memo[m][n];
        }

        if(m>0){
            memo[m-1][n] = num_path(m-1, n);
            a =     memo[m-1][n];
        }else{
            a = 0;
        }

        if(n>0){
            memo[m][n-1] = num_path(m, n-1);
            b = num_path(m, n-1);
        }else{
            b = 0;
        }


        memo[m][n] = a+b;
        return memo[m][n];
    }


    public static void main(String[] args) {
        long beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기


        System.out.println(num_path(4, 4));
        System.out.println(path_memo(4, 4));

        long afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
        long secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
        System.out.println("시간차이(m) : "+secDiffTime);


        //view(map);

        System.out.println("v=============");

        view(memo);
    }


    public static void view(int [][] arr){
        for(int i=0; i < 5; i++){

            for(int j=0; j < 5; j++){
                System.out.printf(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}