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

queue 를 이용한 BFS. DFS 로 하면 시간초과 나온다.

int solution(vector<vector<int> > maps)
{
	int answer = 2147000000;
	int checkX[4] = { -1, 0, 1, 0 };
	int checkY[4] = { 0, 1, 0, -1 };

	vector<vector<int>> check(maps.size(), vector<int>(maps[0].size(), 1));
	vector<vector<int>> saveCount(maps.size(), vector<int>(maps[0].size(), 0));
	check[0][0] = 0;
	saveCount[0][0] = 1;

	queue<pair<int, int>> q;
	q.push({ 0, 0 });

	while (!q.empty())
	{
		for (int i = 0; i < 4; i++)
		{
			int x = q.front().first + checkX[i];
			int y = q.front().second + checkY[i];
			if ((x >= 0 && x < maps.size()) && (y >= 0 && y < maps[0].size()))
			{
				if (check[x][y] == 1 && maps[x][y] == 1)
				{
					q.push({ x, y });
					saveCount[x][y] = saveCount[q.front().first][q.front().second] + 1;
					check[x][y] = 0;
					if (x == maps.size() - 1 && y == maps[0].size() - 1)
					{
						answer = std::min(answer, saveCount[x][y]);
					}					
				}
			}
		}
		q.pop();
	}
	return answer == 2147000000 ? -1 : answer;
}