DP(2)

행렬경로문제

행렬 경로 문제는 우상단에서 좌하단까지 이동하는 방법이다. 단 오른쪽이나 아래쪽방향으로만 움직일 수 있다. 

방문칸에 가중치를 최소화하여 이동해야한다. 

위와 같이 해결하는 방법이다. 

이 문제를 해결하기 위해 우리는 동적계획법을 사용해야하는데 

동적 계획법의 절차는 

1. 순환식을 세운다. 

2. 순환식을 계산하는 방식이다. 

(i, j)까지 이동하는 방법의 이전 단계에서는 (i-1, j)이거나 (i, j-1)에서 이동하는 방법이다. 결과가 모두 최선이 되어야 하기 때문에 각각의 상황 (i-1, j)과 (i, j-1)는 최선의 상황이어야 한다. 

 

순환식

mij는 (i, j)의 가중치이다. L[i, j]는 1, 1에서 부터 i, j 까지의 가중치이다.

 

첫번째 경우는 첫시작이니 당연히 첫번째 값의 값이 나올 것이다. 

두번째 경우는 j = 1이면 j 방향으로 움직일 수가 없다.  

세번째 경우는 i = 1이면 i 방향으로 움직일 수가 없다. 

네번째 경우는 왼쪽이랑 위쪽에서 오는 경우 중 어디가 더 작은지 min값을 꺼내온 후 그 곳의 가중치와 더한 값이다. 

 

이러한 순환식을 c언어로 표현해보겠습니다.

int mat(int i, int 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];
  }

하지마 위와 같이 코드를 작성할 시에는 재귀적으로 자주 호출이 됩니다. 

계산식을 보면 반복되는 방법이 많습니다. 그래서 우리는 메모제이션과 bottomUp방식을 사용하면 좋습니다. 

 

Memoization

int mat(int i, int j){
	if(m[i][j] != -1) return m[i][j];
	if(i==1 && j==1)
		m[i][j] = m[i][j];
    else if(i==1)
    	m[i][j] = mat(1, j-1) + m[i][j];
    else if(j==1)
		m[i][j] = mat(i-1, 1) + m[i][j];
    else 
		m[i][j] = Math.min(mat(i-1, j), mat(i, j-1)) + m[i][j];
    return m[i][j];
  }

메모제이션의 경우 메모해두어서 반복하지 않고 기록해두어서 필요할 때 반환해준다.

 

bottomUp의 경우 

구할려고 하는 값보다 이전의 값들이 필요하다 그래서 위의 점과 옆의 점의 가중치가 필요한데 이는 행을 기준으로 계산할겨냐 열을 기준으로 계산할거냐에 달려있다. 이 문제의 경우에는 행을 기준으로 정렬하면 된다. 

아래의 사진과 같이 행을 기준으로 이동을 해주면 된다. 

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] = m[i][j] + L[i][j-1];
else if (j==1)
	L[i][j] = m[i][j] + L[i-1][j];
else 
	L[i][j] = m[i][j] + Math.min(L[i-1][j], L[i][j-1]);
 }
 }
 return L[n][n];
 }

시간 복잡도는 O(n ^2)이다. 

문제의 내용에 비해 코드가 너무 복잡하다. 그래서 이를 줄여주기 위한 트릭이 있다. 이는 0번째 칼럼과 0번째 인덱스에 값을 무한대로 바꾸는 것이다. 무한대로 바꾸어주면 valid한 값이 아니기 때문에 i==1일 때나 j==1일 때 무한대인 값보다 작은값이 나올 것이다. 

 

그래서 코드는 아래와 같이 작성할 수 있다. 

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 
			L[i][j] = m[i][j] + Math.min(L[i-1][j], L[i][j-1]);
 		}
 	}
	 return L[n][n];
 }

어떻게 이동하고 있나 경로가 궁금할 때도 있을 것이다. 이는 또 다른 배열 하나를 만들어서 값을 넣어 줄때 마다 방향이나 위치 정보를 넣어주면 될 것 같다.

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];
            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];
 }