2-2

행렬 경로 문제

• nxn 행렬에서 오른쪽이나 아래쪽 방향으로만 이동 가능.

• 방문한 칸에 있는 정수들의 합이 최소화되도록 하라.

다익스트라로 풀 수 있지만, 동적 계획법으로 풀어보자.(주제니까)

피보나치, 조합에 대해 순환식으로 풀어봤다. 얘네는 순환식이 주어져서 그대로 풀었다.

대부분의 동적계획법 알고리즘은 주어진 순환식을 푼다기 보다는

• 문제를 풀기 위해 필요한 순환식을 스스로 수립.

• 세워진 순환식을 메모이제이션, bottomUp으로 만드는건 처음엔 어렵지만 하다보면 기계적으로 풀게됨.

(i,j)에 도달하기 위해 (i, j-1) or (i-1, j) 까지 최선의 방법으로 이동해야함.

• L[i,j] : (1,1)에서 (i,j)까지 이르는 최소합

  • m(i,j) // if i=1 and j=1

  • L(i-1, j) + m(i,j) // if j = 1;

  • L(i, j-1) + m(i,j) // if i = 1;

  • min(L(i-1, j), L(i, j-1)) + m(i,j) // otherwise, general case

순환식을 세울 때 가장 중요한 거

• general Case

• base case

위 2가지를 완전하게 세우는 것.

tom-down

bottom-up

왼쪽에 있는 값보다, 오른쪽에 있는 값이 먼저 계산되는 방식.

만약 경로를 구해야 한다면,

각 경로에 최소값인 이전경로의 값을 저장.

int paths[5][5];
int pathSums[5][5];
int minimumPath[5][5];

int direction[2][2] = {
    {-1, 0}, // up
    {0, -1} // left
};

int recursiveVisit(int row, int col) {
    // basecase
    // 출발점이면 return paths[0][0]
    if(row == 0 && col == 0) {
        return paths[0][0];
        minimumPath[0][0] = -1;
    } else if(row == 0) {
        pathSums[0][col] = recursiveVisit(0, col - 1) + paths[0][col];
        minimumPath[row][col] = 1;
    } else if(col == 0) {
        pathSums[row][col] = recursiveVisit(row - 1, 0) + paths[row][0];
        minimumPath[row][col] = 0;
    } else {
        int moveUp = recursiveVisit(row - 1, col);
        int moveLeft = recursiveVisit(row, col - 1);
        if(moveUp < moveLeft) {
            minimumPath[row][col] = 0;
            pathSums[row][col] = moveUp + paths[row][col];
        } else {
            minimumPath[row][col] = 1;
            pathSums[row][col] = moveLeft + paths[row][col];
        }
    }
    return pathSums[row][col];
}

void printMinPath(int row, int col) {
    if(row == 0 && col == 0) {
        return;
    }

    int dirIndex = minimumPath[row][col];

    printMinPath(row + direction[dirIndex][0], col + direction[dirIndex][1]);

    cout<<"("<<row<<", "<<col<<")"<<endl;
}


int main(int argc, const char * argv[]) {

    for(int i = 0; i<5; i++) {
        for(int j=0; j<5; j++) {
            cin>>paths[i][j];
        }
    }

    cout<<recursiveVisit(4, 4)<<endl;
    printMinPath(4,4);

    return 0;
}

Summary

DP는 주어진 순환식을 푼다기 보다는, 문제를 풀기 위해 필요한 순환식을 스스로 수립. 세워진 순환식을 메모이제이션, bottomUp으로 만드는 건 처음엔 어려운데 기계적으로 풀게됨.

bottomUp으로 풀게 될 경우, 왼쪽에 있는 값보다 오른쪽에 있는 값이 먼저 계산됨.