[프로그래머스 lv 2 ] - 게임 맵 최단거리

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

#include <vector>
#include <queue>
#include <string.h>
#define MAX 10001 //100x100 맵 최대크기의 최악의 경로는 10000이므로 10001 선언 
using namespace std;

int dis[100][100] ;
int dir[4][2] = {
	{1,0}//하
	,{0,1} //우
	,{-1,0} //상
	,{0,-1}//좌
};

int solution(vector<vector<int>> maps)
{
	int answer = 0;

	memset(dis, MAX, sizeof(dis));

	dis[0][0] = 1;
	queue<pair<int, int>> q;
	int sizeX = maps.size();
	int sizeY = maps[0].size();    

	q.push({ 0,0 });

	while (!q.empty())
	{
		int curX = q.front().first;
		int curY = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nextX = curX + dir[i][0];
			int nextY = curY + dir[i][1];

			if (nextX < 0 || nextY < 0 || sizeX <= nextX || sizeY <= nextY)
				continue;
			if (maps[nextX][nextY] == 1 && (dis[nextX][nextY] > dis[curX][curY] + 1))
			{
				dis[nextX][nextY] = dis[curX][curY] + 1;
				q.push({ nextX,nextY });
			}
		}
	}
	answer = dis[sizeX - 1][sizeY - 1];
	if (answer == 286331153) //memset 함수 값이 unsigned char라서 286331153이라는 값으로 초기화 된 상태 
	{
		return -1;
	}
	else
	{
		return answer;
	}
	
}