[프로그래머스] 게임 맵 최단거리 (C++)

문제

프로그래머스

이 문제는 n * m 크기의 0(벽), 1(길)로 이루어진 Map에서 (1,1) 부터  (n,m)까지의 최단 거리를 구하는 문제이다.

---

풀이

(0,0) 부터 (n-1,m-1)까지 탐색하는 걸로 풀이했다.

BFS를 이용하여 (n-1,m-1)까지의 각 타일 별 최단 거리를 구했다.

#include<vector>
#include<queue>
#include <iostream>

using namespace std;

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


int BFS(vector<vector<int> > maps){
    int m = maps[0].size(), n = maps.size();
    queue<pair<int, int>> q;
    q.push({0,0});
    
    while(!q.empty()){
        int posY = q.front().first;
        int posX = q.front().second;
        
        if(posY == n - 1 && posX == m - 1){
           return maps[n - 1][m - 1];
        }
        
        q.pop();
        
        for(int i = 0; i< 4; i++){
            int moveY = posY + dy[i];
            int moveX = posX + dx[i];
            
            if(moveX < 0 || moveY < 0 || moveX >= m || moveY >= n)
                continue;
            
            if(maps[moveY][moveX] == 1){
                maps[moveY][moveX] = maps[posY][posX] + 1;
                q.push({moveY, moveX});
            }
        }
    }
    
    return 0;
}
int solution(vector<vector<int> > maps)
{
    int answer = BFS(maps);
    if(answer == 0)
        return -1;
    
    return answer;
}