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

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

프로그래머스

BFS 를 이용하여 경로를 탐색하면 되는데, dist 배열을 활용하여 갈 수 있는 경로까지 소요되는 시간(?)을 기록한다. 이때 dist 배열을 초기에 -1 로 설정하면 visit 배열을 따로 두지 않고도 방문 여부 체크가 가능하다.

 

[C++]

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

using namespace std;

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

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    // n x m ,  1 ~ n,m ~ 100
    // 0 : 벽  1 : 길
    
    int n = maps.size(); int m = maps[0].size();
    
    for(int i = 0 ; i < n; i++)
        fill(dist[i], dist[i]+m, -1);
    
    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 0;
    
    while(!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        
        for(int dir = 0 ; dir < 4 ; dir ++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            
            if(nx<0 || nx>= n || ny<0 || ny>=m) continue; // out of bounds
            if(maps[nx][ny] == 0 || dist[nx][ny] > 0) continue;
            
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            q.push({nx, ny});
        }
        
    }
    
    answer = dist[n-1][m-1];
    return answer == -1 ? -1 : answer+1;
}