[프로그래머스] 게임 맵 최단거리

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

BFS 알고리즘을 사용하여 (1, 1)에서 (n, m)까지 이동횟수를 체크하면 된다.
배열의 인덱스는 0부터 시작하므로 (0, 0)에서 (n-1, m-1)까지 이동횟수로 해결하였다.

코드

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

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

int bfs(vector<vector<int>>& maps){
    int ret = 0;
    int m = maps.size();
    int n = maps[m-1].size();
    vector<vector<int>> visited(m, vector<int>(n, 0));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = 1;


    while(!q.empty()){
        pair<int, int> cur = q.front();
        q.pop();

        for(int i=0; i<4; i++){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if(nx < 0 || nx > n-1 || ny < 0 || ny > m-1) continue;
            if(visited[ny][nx] == 0 && maps[ny][nx] == 1){
                visited[ny][nx] = visited[cur.second][cur.first] + 1;
                q.push({nx, ny});
            }
        }
    }
    if(visited[m-1][n-1] == 0) ret = -1;
    else ret = visited[m-1][n-1];
    return ret;
}

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