Programmers_게임 맵 최단거리

😒 그냥 딱 전형적인 BFS 문제였다. 무엇인가 함정같은 것도 없고 벽을 뿌시는 것도 없고 그냥 최단거리만 구하면 되는 문제였다.

• 평소 BFS 문제를 풀때 처럼 풀어냈다.
• 최단거리를 구하는 문제기에 움직인 칸의 수는 전 칸의 수에서 더해줬다.
• 오른쪽 끝의 값을 찾으면 return 시킴.(최단거리기에 다른 돌아오는 값은 받을 필요가 없다.)
• 만약 끝칸이 막혀있는 경우를 대비해 BFS를 끝내고 나온 경우의 return -1을 해준다.

#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>

using namespace std;

int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
int check[101][101];
int cnt [101][101];

int bfs(vector<vector<int> > maps)
{
    queue<pair<int,int>>q;
    q.push({0,0});
    check[0][0]=1;
    memset(cnt,10001, sizeof(cnt));
    cnt[0][0]=1;
    
    while(!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        if(y==maps.size()-1 && x == maps[0].size()-1) return cnt[maps.size()-1][maps[0].size()-1];
        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= maps.size() || nx >= maps[0].size() || ny <0 || nx<0) continue;
            if(!check[ny][nx] && maps[ny][nx]==1)
            {
                q.push({ny,nx});
                check[ny][nx]=1;
                cnt[ny][nx] = min(cnt[ny][nx], cnt[y][x]+1);
            }
        }
    }
    return -1;
}

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

이제 슬슬 3단계 풀어봐야겠다. 2단계는 너무 쉽다. 근데 이게 왜 2단계지