백준(BOJ) 1261 알고스팟 2 **

다익스트라 알고리즘을 이용하여 풀었다.


1. 현재 노드에서 갈수 있는곳 중 가장 적은 비용인 노드를 선택한다.
 2. 노드로 이동 후, 노드에 가는 비용을 업데이트한다.

배운점
* 128MB이면 배열의 크기는 대략 5000*5000을 넘으면 안된다.
* 반례가 모두 성립되었는데도 해결이 되지 않았다면 간단한 실수를 조심하자.

#include 
#include 
#include 
#include 
#include 
#define MAX 10005
#pragma warning(disable:4996)
using namespace std;

int ori[105][105], node_n,node[2][20005], x,y;
int dy[4] = { 0,-1,0,1 }, dx[4] = { -1,0,1,0 };
char ch[105];
vector> v[20005];

int getMin(void)
{
	int mi = -1, val = MAX;
	for (int i = 1; i <= y*x; i++)
	{
		if (node[1][i] == 0 && node[0][i] < val)
		{
			val = node[0][i];
			mi = i;
		}
	}
	if (mi != -1)
		node[1][mi] = 1;
	return mi;
}
// 1. 현재 노드에서 갈수 있는곳 중 가장 적은 비용인 노드를 선택한다.
void update(int str)
{
	for (int i = 0; i < v[str].size(); i++)
	{	
		if(v[str].at(i).second + node[0][str] < node[0][v[str].at(i).first])
			node[0][v[str].at(i).first] = v[str].at(i).second + node[0][str];
	}
}
// 2. 노드로 이동 후, 노드에 가는 비용을 업데이트한다.
void djk(void)
{
	int next = 1;
	while (next != -1)
	{
		update(next);
		next = getMin();
	}
}
// 
// 다익스트라 알고리즘
int main()
{
	fill_n(&ori[0][0], 105*105, MAX);
	fill_n(&node[0][0], 20005 * 2, 0);
	fill_n(&node[0][0], 20005, MAX);

	scanf("%d %d", &x, &y);

	for (int i = 1; i <= y; i++)
	{
		scanf("%s", ch);
		for (int k = 1; k <= x; k++)
			ori[i][k] = ch[k - 1] - '0';
	}

	for (int i = 1; i <= y; i++)
		for (int k = 1; k <= x; k++)
			for (int q = 0; q < 4; q++)
			{
				v[(i - 1)*x + k].push_back(make_pair((i - 1 + dy[q])*x + k + dx[q], ori[i + dy[q]][k + dx[q]]));
			}

	node[0][1] = 0;
	node[1][1] = 1;

	djk();

	printf("%d", node[0][y*x]);
	return 0;
}