[Programmers] 게임 맵 최단거리

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

int solution(vector<vector<int> > maps)
{
    int n = maps.size();
    int m = maps[0].size();
    int check[n][m];
    queue<pair<int,int>> q; 
    int deltaX[4] = {-1,0,1,0};
    int deltaY[4] = {0,1,0,-1};
    
    q.push(make_pair(0,0));
    check[0][0] = 1;
    int x,xx,y,yy;
    while(!q.empty()){
        yy = q.front().first;
        xx = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            x = xx + deltaX[i];
            y = yy + deltaY[i];
            
            if(x<0||y<0||x>m-1||y>n-1) continue;
            if(maps[y][x] == 0) continue;
            if(check[y][x] == 1) continue;
            
            check[y][x] = 1;
            q.push(make_pair(y,x));
            maps[y][x] = maps[yy][xx] + 1;
            
        }
    }

    if(check[n-1][m-1] !=1 ) return -1;
    return maps[n-1][m-1];
}

queue를 이용한 탐색 문제였다. 따로 가중치가 없으므로 BFS를 이용하면 최단거리를 구할 수 있다.

처음에는 일단 queue에 넣고, 빼냈을 때 벽인지, 방문한 좌표인지, 맵 인덱스를 넘어가지 않는지를 확인했는데 계속 buffer overflow 오류가 나서 포기하고 다른 블로그 풀이를 참조했다.

먼저 queue에 삽입 전에 조건을 확인하였는데, 확실히 이렇게 하는 게 좀 더 효율적일 것 같다. 작업 하나를 덜 해도 되니까.

그리고 delta 배열을 이용해 상하좌우를 확인하였는데 이게 코드가 더 깔끔해진다.

도착지점이 항상 1인 상태인 경우만 생각했는데, 이미 도착지점이 0인 경우도 있어서 마지막에 check배열을 이용해 도착지점에 방문한 적이 있는지 확인하였다.