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

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

---

 

-풀이-

일반적인 최단거리를 구하는 bfs문제이다.

근데 주의를 할점이 visited[100][100] 을 전역변수가아닌 지역변수로 할당하니 효율성 테스트에서 0점이 나왔다.

전역변수로 만들어주자

 

-시간 복잡도-

bfs이므로 O(N*N)이 된다.

 

-코드-

 

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

int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool visited[100][100];
bool isIn(int i,int j,int n,int m){
    return i>=0&&i<n&&j>=0&&j<m;
}

int solution(vector<vector<int> > maps)
{
    queue<pair<pair<int,int>,int>> q;
   
    int n=maps.size();
    int m=maps[0].size();
    q.push({{0,0},1});
    visited[0][0]=true;
    
    while(!q.empty()){
        int i=q.front().first.first;
        int j=q.front().first.second;
        int cnt=q.front().second;
        q.pop();
        
        if(i==n-1&&j==m-1){
            return cnt;
        }
        
        for(int k=0;k<4;k++){
            int ni=i+mv[k][0];
            int nj=j+mv[k][1];
            
            if(isIn(ni,nj,n,m)&&!visited[ni][nj]&&maps[ni][nj]==1){
                q.push({{ni,nj},cnt+1});
                visited[ni][nj]=true;
            }
        }
    }
    return -1;
}