동적 계획법 (2) - 경로 탐색

Dynamic Programming

Basic Problem

행렬 경로 문제

- 정수들이 저장된 N X N 행렬의 좌상단부터 우하단까지 이동한다. 단 오른쪽 또는 아래 방향으로만 이동이 가능하다.

- 방문한 칸에 있는 정수들의 합이 최소화되도록 프로그래밍해라.

행렬 - Key Obervation

- (i, j)에 도달하기 위해서는 (i, j - 1)이나 (i - 1, j)를 거쳐야 한다.

- 또한 (i, j - 1) 혹은 (i - 1, j)가지는 최선의 방법으로 이동해야 한다.

행렬 - 순환식

- L[i, j] : (1, 1)부터 (i, j)까지 도달하는 최소 경로의 길이 합

$m_{ij}$는 (i, j)위치에 저장되어 있는 숫자를 의미한다.

i와 j가 각각 1일때는 가장 구석에 위치해 있는 것으로 각각 오른쪽과 아래쪽으로만 움직일 수 없는 상태이다.

행렬 - Recursion

int mat (int i, int j) { // L(i, j)의 값을 계산해주는 메소드

if (i == 1 && j == 1)

return m[i][j];

else if (i == 1)

return mat(1, j - 1) + m[i][j];

else if (j == 1)

return mat(i - 1, 1) + m[i][j];

else

return Math.min (mat(i - 1, j), mat(i, j - 1)) + m[i][j];

}

-> Recursion방식은 중복이 많이 발생하여 비효율적이다.

행렬 개선 - Memorization

int mat (int i, int k) {

if (L[i][j] != -1)

return L[i][j];

if (i == 1 && j == 1)

L[i][j] = m[i][j];

else if (i == 1)

L[i][j] = mat(1, j - 1) + m[i][j];

else if (j == 1)

L[i][j] = mat(i - 1, 1) + m[i][j];

else

L[i][j] = Math.min (mat(i - 1, j), mat(i, j - 1)) + m[i][j];

return L[i][j];

}

행렬 개선 - Bottom Up

- 기본적으로 방향이 정해져 있는 것이 아니라 순환식의 왼쪽 값보다 오른쪽의 값이 항상 먼저 계산되는 것이 Bottom-Up방식이 된다.

int mat() {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if (i == 1 && j == 1)

L[i][j] = m[i][j];

else if (i == 1)

L[i][j] = L[1, j - 1] + m[i][j];

else if (j == 1)

L[i][j] = L[i - 1, 1] + m[i][j];

else

L[i][j] = Math.min (L[i - 1, j], L[i, j - 1]) + m[i][j];

}

}

return L[i][j];

}

- 조건식의 아래 3가지 경우를 하나로 합칠 경우 i나 j가 1일 때 제일 아래 식의 인덱스가 0이 되어 오류가 발생한다.

행렬 - Common Trick

- 조건식을 복잡하게 여러개로 나누지 않기 위해 간단한 트릭을 사용한다.

- 제일 왼쪽과 위쪽 배열을 전부 무한대로 채워놓으면 조건식을 복잡하게 나눌 필요가 없게 된다.

int mat() {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if (i == 1 && j == 1)

L[i][j] = m[1][1];

else

L[i][j] = m[i][j] + Math.min(L[i - 1][j], L[i][j - 1]);

}

}

return L[n][n];

}

-> 위 코드의 시간 복잡도는 $O(n^2)$이 된다.

행렬의 경로 구하기

- 경로를 구하기 위해서는 추가적인 배열을 만들어 이전에 선택했던 행렬의 방향값을 저장해준다.

int mat() {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

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

L[i][j] = m[1][1];

P[i][j] = '-';

}

else {

if (L[i - 1][j] < L[i][j - 1]) {

L[i][j] = m[i][j] + L[i - 1][j];

P[i][j] = '←';

} else {

L[i][j] = m[i][j] + L[i][j - 1];

P[i][j] = '↑';

}

}

}

}

return L[n][n];

}

//(arraylength, arraylength)좌표부터 시작하여 (0, 0)까지 되짚어가며 경로를 출력

void printPath() {

int i = n, j = n;

while (P[i][j] != '-') {

System.out.print(i + " " + j);

if (P[i][j] == '←')

j--;

else

i--;

}

System.out.print(i + " " + j);

}

//(0, 0)부터 거슬러 올라가는 방법

void printPathRecursive(int i, int j) {

if (P[i][[j] == '-')

System.out.print(i + " " + j);

else {

if (P[i][j] -- '←')

printPathRecursive(i, j - 1);

else

printPathRecursive(i - 1, j);

System.out.print(i + " " + j);

}

}