(c++) 프로그래머스 "게임 맵 최다거리"

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

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

---

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

vector<int> x = { 1,0,0,-1 };
vector<int> y = { 0,1,-1,0 };
int n, m;

int solution(vector<vector<int>> maps)
{
	int answer = 0;
	queue<pair<int, int>> q;
	n = maps.size(); m = maps[0].size();
	q.push({ 0,0 });
	while (!q.empty()) {
		int nowx = q.front().first;
		int nowy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = nowx + x[i];
			int ny = nowy + y[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1) {
				maps[nx][ny] = maps[nowx][nowy] + 1;
				q.push({ nx,ny });
			}
		}
	}
	return maps[n - 1][m - 1] > 1 ? maps[n - 1][m - 1] : -1;
}

왜 큐를 하면 가장 작은 값인지 확인 안해도 되고 스택하면 작은지 확인해야하지?

=> 스택은 같은 길을 2번 간다.

why? 갈림길 1에서 2가지 선택지가 있다면 첫번째 선택지를 가는 동안 만나는 갈림길의 선택지가 우선시되기 때문

=> 큐는? 2가지 선택지를 번갈아가면서 보기때문에 동시에 움직이는 듯한 느낌을 준다.