[프로그래머스/C++]Lv.2 게임 맵 최단거리(BFS)

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

소스코드

#include<vector>
#include <queue>
using namespace std;

class Position
{
public:

	Position() : PosY(0), PosX(0)
	{
	}

	Position(int _posY, int _posX)
	{
		this->PosX = _posX;
		this->PosY = _posY;
	}

public:
	int PosY;
	int PosX;
};

int BFS(vector<vector<int>> maps)
{
	const int maxY = maps.size(); // n 행
	const int maxX = maps[0].size(); // m 열

	vector<int> dx{ -1, 1, 0, 0 };
	vector<int> dy{ 0, 0, -1, 1 };

	queue<Position*> q;
	q.push(new Position());

	vector<vector<int>> visited(maxY, vector<int>(maxX, -1));
	vector<vector<int>> dist(maxY, vector<int>(maxX, -1));
	dist[0][0] = 1;
	visited[0][0] = 1;

	while (q.empty() == false)
	{
		Position* nowPos = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = nowPos->PosY  + dx[i];
			int nextX = nowPos->PosX + dy[i];
		
			if (nextY < 0 || nextY >= maps.size())
				continue;

			if (nextX < 0 || nextX >= maps[0].size())
				continue;

			if (maps[nextY][nextX] == 0)
				continue;

			if (visited[nextY][nextX] == 1)
				continue;

			q.push(new Position(nextY, nextX));
			visited[nextY][nextX] = 1;
			dist[nextY][nextX] = dist[nowPos->PosY][nowPos->PosX] + 1;

		}
	}

	 return dist[maxY - 1][maxX - 1];
}

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

	answer = BFS(maps);

	return answer;
}