1249. [S/W 문제해결 응용] 4일차 - 보급로

이건...솔직히 풀다가 답을 봤다..ㅎㅎ

거의 비슷하긴 했는데..2%가 부족했다!!!!!

BFS를 이용하며 모든 맵을 탐색한다. 그리고 map 이외의 배열을 하나 더 만들어

해당 좌표에 오는 최단 시간을 계속 갱신하면 된다>! 

백준에 이거랑 비슷한 문제를 풀었던 것 같은데 기억이 안 난다..그때는 BFS말고 다른 방법으로 풀었었는데....메모이 제이션으로 풀었었나.....내일은 새로운 방법으로 풀어봐야지!!!

#include <stdio.h>
#include <string.h>
int map[111][111];
int visit[111][111];
int Q[2][100 * 100 * 100];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int Q_Front, Q_Back;
int main()
{
	int Test;
	scanf("%d",&Test);
	for (int i = 1; i <= 10; i++)
	{
		int Lenth;
		scanf("%d", &Lenth);
		Q_Front = Q_Back = -1;
		memset(map, -1, sizeof(map));
		memset(Q, 0, sizeof(Q));
		for (int a = 1; a <= Lenth; a++)
		{
			for (int b = 1; b <= Lenth; b++)
			{
				scanf("%1d", &map[a][b]);
				visit[a][b] = _CRT_INT_MAX;
			}
		}
		Q[0][++Q_Back] = 1;
		Q[1][Q_Back] = 1;
		visit[1][1] = 0;
		while (Q_Back!=Q_Front)
		{
			int x = Q[0][++Q_Front];
			int y = Q[1][Q_Front];
			for (int a = 0; a < 4; a++)
			{
				int xx = x + dx[a];
				int yy = y + dy[a];
				if (xx<1 || yy<1 || xx >Lenth || yy >Lenth)
					continue;
				if (visit[yy][xx]>(map[yy][xx] + visit[y][x]))
				{
					visit[yy][xx] = map[yy][xx] + visit[y][x];
					Q[0][++Q_Back] = xx;
					Q[1][Q_Back] = yy;
				}
			}
		}
		printf("#%d %d\n", i, visit[Lenth][Lenth]);
	}
	return 0;
}