[C++] 게임 맵 최단거리

[문제]

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

프로그래머스

[문제 풀이]

BFS를 활용한 최소 거리 구하기 문제이다.

0,0에서 n,m까지의 2차원 평면에서 최소 거리를 구해야 하기 때문에 DFS가 아니라 BFS를 활용해야 한다.

[코드]

#include<vector>
#include<queue>

using namespace std;

int visited[101][101];

int bfs(vector<vector<int> > maps,int n, int m){
    
    int result = 0;    
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};
    
    queue<pair<pair< int, int>,int > > ror;
    ror.push(make_pair(make_pair(0,0),1));
    
    while(ror.size() > 0){
        int curX = ror.front().first.first;
        int curY = ror.front().first.second;
        int curCount = ror.front().second;
        
        if(curX == n-1 && curY == m - 1){
            result = curCount;
        }
        
        ror.pop();
        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(nextX >= 0 && nextX < n && nextY >=0 && nextY < m){
                if(maps[nextX][nextY] == 1){
                    if(visited[nextX][nextY] == 0){
                        visited[nextX][nextY] = 1;
                        ror.push(make_pair(make_pair(nextX, nextY),curCount + 1));
                    }
                }
            }
        }
    }
    
    if(result == 0){
        return -1;
    }
    
    return result;
}

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    answer = bfs(maps, maps.size(), maps[0].size());
    return answer;
}