96. 알리바바와 40인의 도둑(Bottom-Up) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include <iostream>
#include <queue>

using namespace std;

int dy[20][20];
int a[20][20];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, p1 = 0, p2 = 0;
	
	cin >> n;
	
	int X[2] = {0, 1};
	int Y[2] = {1, 0};
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}
	}
	
	dy[0][0] = a[0][0];
		
	while(true)
	{
		if(p1 >= n || p2 >= n)
			break;
		
		for(int i = 0; i < 2; i++)
		{
			if(dy[p1+X[i]][p2+Y[i]] == 0)
				dy[p1+X[i]][p2+Y[i]] = dy[p1][p2] + a[p1+X[i]][p2+Y[i]];
			else
			{
				if(dy[p1][p2] + a[p1+X[i]][p2+Y[i]] < dy[p1+X[i]][p2+Y[i]])
					dy[p1+X[i]][p2+Y[i]] = dy[p1][p2] + a[p1+X[i]][p2+Y[i]];
			}
		}
		
		p2++;
		if(p2 >= n)
		{
			p2 = 0;
			p1++;
		}
	}
	
	cout << dy[n-1][n-1] << "\n";
	
	return 0;
	
}

출발지점 (0,0)에서부터 (3,3) 까지 최소비용으로 가는 방법을 다이나믹 프로그래밍으로 풀어보는 문제다. (bottom - up)

알리바바는 오른쪽과 아래로만 이동할 수 있다. 이는 X, Y 배열을 활용하고, 알리바바의 현재 위치는 p1, p2로 결정한다.

while(true)
	{
		if(p1 >= n || p2 >= n)
			break;
		
		for(int i = 0; i < 2; i++)
		{
			if(dy[p1+X[i]][p2+Y[i]] == 0) // 다음으로 갈 위치가 다른 방향에서 방문 안 했다면
				dy[p1+X[i]][p2+Y[i]] = dy[p1][p2] + a[p1+X[i]][p2+Y[i]];
			else
			{
				if(dy[p1][p2] + a[p1+X[i]][p2+Y[i]] < dy[p1+X[i]][p2+Y[i]]) // 방문했었더라면
					dy[p1+X[i]][p2+Y[i]] = dy[p1][p2] + a[p1+X[i]][p2+Y[i]];
			}
		}
		
		p2++;
		if(p2 >= n)
		{
			p2 = 0;
			p1++;
		}
	}

위 코드가 조금 복잡해보이므로 아래 그림으로 설명하겠다.

주황색의 위치는 (1,2)에서 아래로 갈 때, (2,1)에서 오른쪽으로 갈 때로 겹치게 된다. 이 때 최소비용으로 가야하기 때문에 둘 중 더 작은 값이 들어가게 된다.