ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 한빛 알고리즘 chapter8 동적프로그래밍 행렬경로문제
    최적화_통계_알고리즘/알고리즘 2012.07.16 00:39

    봄싹 텔레파시 스터디에서 스터디한 내용으로 작성해봤습니다~~

    Top Down, Bottom Up 2가지 방식을 모두 사용하는 형식의 인터페이스를 했더니 약간

    인터페이스부분이 깔끔하지 않네요...ㅠㅠ


    -----------------------------------------------------------------------------------------------------------

    public interface MatrixPath {

    /**

    * @param dataA   데이터용 2차원 배열

    * @param resultA 결과저장용 2차원 배열

    * @param row     결과요청 row    

    * @param col     결과요청 col

    * @return 최종 결과값

    */

    public int matrixPath(int[][] dataA, int[][] resultA, int row, int col);

    }


    -----------------------------------------------------------------------------------------------------------

    //[Top down 방식:재귀형식]

    public class DonghunMatrixPath implements MatrixPath {


    @Override

    public int  matrixPath(int[][] dataA, int[][] resultA, int i, int j) {


    int result = 0;

    if(i==0 && j == 0){

    result = dataA[i][j];

    }else if(i==0){

    result = dataA[i][j] + matrixPath(dataA, resultA, 0, j-1);

    }else if(j==0){

    result = dataA[i][j] + matrixPath(dataA, resultA, i-1, 0);

    }else{

    result = dataA[i][j] + max(matrixPath(dataA, resultA, i-1, j), matrixPath(dataA, resultA, i, j-1));

    }

    resultA[i][j] = result;

    return result;

    }

    private int max(int a, int b){

    if(a>b){

    return a;

    }else{

    return b;

    }

    }

    }


    -----------------------------------------------------------------------------------------------------------

    //[Bottom up 방식:재귀]

    public class DonghunMatrixPathBottomUp implements MatrixPath{


    @Override

    public int matrixPath(int[][] dataA, int[][] resultA, int row, int col) {


    int result = 0;

    for(int i=0; i <= row; i++ ){

    for(int j=0; j <= col; j++){

    if(i==0 && j==0){

    result = dataA[0][0];

    }else if(i==0){

    result = dataA[0][j] + resultA[0][j-1];

    }else if(j==0){

    result = dataA[i][0] + resultA[i-1][0];

    }else{

    result = dataA[i][j] +  max(resultA[i-1][j], resultA[i][j-1]);

    }

    resultA[i][j] = result;

    }

    }

    return result;

    }


    private int max(int a, int b){

    if(a>b){

    return a;

    }else{

    return b;

    }

    }


    }

    ------------------------------------------------------------------------------------------------------------------
    //Test code
    public class DonghunMatrixPathTest {

    //입력데이터 
    static int[][] dataA = {
    { 6, 7, 12,  5},
    { 5, 3, 11, 18},
    { 7,17,  3,  3},
    { 8,10, 14,  9}
    };

    @Test
    public void testMatrixPath(){
    int[][] resultA = new int[4][4];
    MatrixPath path = new DonghunMatrixPath();
    int result = path.matrixPath(dataA, resultA, 3, 3);

    System.out.println("[result Array:TopDown(Recursive)]");
    print(resultA);
    Assert.assertEquals(68, result);
    }
    @Test
    public void testMatrixPathBottomUp(){
    int[][] resultA = new int[4][4];
    MatrixPath path = new DonghunMatrixPathBottomUp();
    int result = path.matrixPath(dataA, resultA, 3, 3);

    System.out.println("[result Array:BottomUp]");
    print(resultA);
    Assert.assertEquals(68, result);
    }
    private void print(int[][] data){
    for(int i=0; i < data.length; i++){
    for(int j=0; j < data[0].length; j++){
    System.out.print(data[i][j] + " ");
    }
    System.out.print("\n");
    }
    }
    }


    댓글 0

Designed by Tistory.