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

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

프로그래머스

 

일반적인 BFS로 풀었다.

각 칸(경로)마다의 가중치가 없기 때문에, 방문처리만 하며 가장 빠르게 목적지에 도달하는 경로가 최단 거리이다.

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

int dy[]{ -1, 0, 1, 0 };
int dx[]{ 0, 1, 0, -1 };

int solution(vector<vector<int>> maps)
{
	int answer = 1;
	vector<vector<bool>> Visit(maps.size(), vector<bool>(maps[0].size(), false));
	queue<pair<int, int>> q;

	q.push({ 0, 0 });

	while (!q.empty())
	{
		int Size = q.size();
		for (int i = 0; i < Size; ++i)
		{
			int y = q.front().first, x = q.front().second;
			q.pop();

			if (Visit[y][x]) continue;
			Visit[y][x] = true;

			for (int j = 0; j < 4; ++j)
			{
				int ny = y + dy[j], nx = x + dx[j];
				if (ny < 0 || nx < 0 || ny > maps.size() - 1 || nx > maps[0].size() - 1 || !maps[ny][nx]) continue;

				if (ny == maps.size() - 1 && nx == maps[0].size() - 1) return ++answer;
				q.push({ ny, nx });
			}
		}
		answer++;
	}
	return -1;
}