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

시간 복잡도

• BFS를 인접행렬을 이용하여 구현하면 $O(V*E)$의 시간 복잡도가 발생합니다.

문제 접근법

• 시작 지점을 기준으로 BFS를 수행하며 시작 지점부터 모든 지점까지의 거리를 업데이트 합니다.
• BFS를 수행 후 $(n, m)$ 까지의 거리가 정답이 됩니다.
• 만약 $(n, m)$을 탐색하지 못했다면 거리가 0이기 떄문에 정답을 -1로 업데이트합니다.

코드

#include<vector>
#include<queue>

using namespace std;

static int n;
static int m;
static int dy[] = {-1, 1, 0, 0};
static int dx[] = {0, 0, -1, 1};
static int dp[101][101]={};
static int visited[101][101] = {};

void BFS(vector<vector<int>>& maps, int y, int x)
{
    queue<pair<int, int>> q;
    q.push({y, x});
    visited[y][x]=true;
    dp[y][x]=1;
    
    while(!q.empty())
    {
        int nowY = q.front().first;
        int nowX = q.front().second;
        
        q.pop();
        
        for(int i=0; i<4; i++)
        {
            int nextY = nowY + dy[i];
            int nextX = nowX + dx[i];
        
            if(nextY >= 0 && nextY < n && nextX>=0 && nextX<m)
            {
                if(!visited[nextY][nextX] && maps[nextY][nextX])
                {
                    visited[nextY][nextX]=true;
                    dp[nextY][nextX] = dp[nowY][nowX]+1;
                    q.push({nextY, nextX});
                }
            }
        
        }
    }
    
}


int solution(vector<vector<int>> maps)
{
    int answer=0;
    n = maps.size();
    m = maps[0].size();
    
    BFS(maps, 0, 0);
    
    if(!dp[n-1][m-1])
        answer = -1;
    else
        answer = dp[n-1][m-1];
    
    
    return answer;
}