한빛 알고리즘 chapter8 동적프로그래밍 행렬경로문제

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

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");
}
}
}