Life in a matrix

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

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;

}

}

}