게임 맵 최단거리/C++

프로그래머스

풀이방법

 

BFS(너비 우선 탐색) 알고리즘을 이용해서 최단거리를 구할 수 있다.

#include <vector>
#include <queue>

using namespace std;

bool check[101][101] = {0};
int board[101][101] = {0};

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

queue<pair<int, int>> q;

int solution(vector<vector<int> > maps) {
    int answer = 0;
    
    int m = maps.size();
    int n = maps[0].size();
    
    q.push({0,0});
    check[0][0] = true;
    board[0][0] = 1;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int curX = dx[i] + x;
            int curY = dy[i] + y;
            
            if(curX < 0 || curX >= m || curY < 0 || curY >= n) continue;
            if(check[curX][curY]) continue;
            if(!maps[curX][curY]) continue;
            
            check[curX][curY] = true;
            q.push({curX, curY});
            board[curX][curY] = board[x][y] + 1;
        }
    }
    
    if(!board[m-1][n-1]) return -1;
    else return board[m-1][n-1];
}