게임 맵 최단거리(Lv2)

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

#include<vector>
#include <queue>
#include <cstring>
#define MAX 10001
using namespace std;
 
int dist[101][101] , mX[] = {-1,0,1,0}, mY[] = {0,1,0,-1};
 
int solution(vector<vector<int> > maps)
{
    memset(dist, MAX, sizeof(dist));
    int N = maps.size(), M = maps[0].size();
    dist[0][0] = 0;
    int answer = 1;
    queue<pair<int, int>>q;
    q.push(make_pair(0,0));
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx = x + mX[i];
            int ny = y + mY[i];
            
            if(nx<0||ny<0||nx>=N||ny>=M) continue;
            if(maps[nx][ny] == 0) continue;
            if(dist[nx][ny] > dist[x][y] + 1){
                dist[nx][ny] = dist[x][y] + 1;
                q.push(make_pair(nx,ny));
            }
            
        }
    }
    if(dist[N-1][M-1] == 286331153) answer = -1;
    else
        answer = dist[N-1][M-1] + 1;
    return answer;
}

위 풀이에서

BFS로 최단거리 찾는 문제 풀 때
1. X/Y 방향 좌표계 4방향 만든다
2. 방문기록 표시 (2차원 0으로 된 벡터)
3. queue<pair<int,int>>에 0넣은 다음, 방문기록으로 방문했다 1표시한다.
4. 조건문으로 while(!queue.empty())일 때까지 반복한다.
5. ㄱ. 1차포문 queue.size()만큼 반복하고, ㄴ.4방향 으로 각각 2중 포문
6. ㄱ. 1차포문에서 x,y 좌표 구하고 ㄴ. 2차 포문에서 다음 x,y 조건 구하고
7. 2차포문에서 바운더리 범위 내에 있고, 방문 안한건지 확인한다.
8. 2차포문 내부에서 목표지점 도달하면 return 하고 아니면 방문표시 하고 queue에 넣어서 bfs한다.

이문제 처음 풀었을때 못풀었던점 :
최단거리 처리할 때
if(dist[nx][ny] > dist[x][y] + 1){
dist[nx][ny] = dist[x][y] + 1;
q.push(make_pair(nx,ny));
}
이렇게가져가면 chk배열이랑 같은방식임.

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dirX[4] = { 1,0,-1,0 };
int dirY[4] = { 0,-1,0,1 };
int chk[101][101] = { 0, };
int Row(0);
int Col(0);
int Rst(1);

int bfs(int starty, int startx, vector<vector<int>>& maps)
{
    chk[starty][startx] = 1;
    queue<pair<int, int>> qTemp;
    qTemp.push(make_pair(starty, startx));
    while (!qTemp.empty())
    {
        int iSize = qTemp.size();
        for (int i = 0; i < iSize; i++)
        {
            int y = qTemp.front().first;
            int x = qTemp.front().second;
            qTemp.pop();

            for (int i = 0; i < 4; i++)
            {
                int ny = y + dirY[i];
                int nx = x + dirX[i];

                if (ny >= 0 && ny < Row && nx >= 0 && nx < Col && maps[ny][nx] == 1 && chk[ny][nx] == 0)
                {
                    if (ny == Row - 1 && nx == Col - 1)
                    {
                        Rst++;
                        return Rst;
                    }
                    chk[ny][nx] = 1;
                    qTemp.push(make_pair(ny, nx));
                }
            }
        }
        Rst++;
    }
    
        
    return -1;
    
}

int solution(vector<vector<int> > maps)
{
    Row = maps.size();
    Col = maps[0].size();

    int iRst = bfs(0, 0, maps);

    return iRst;

}

이 풀이로 바꿈