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

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

굉장히 흔한 유형의 bfs문제이다.
visitMap 관리하면서 row, col, cost 신경써서 queue가 비거나 도착지에 도착할때까지 bfs를 돌려주면 된다.

priority_queue 썼다가 효율성 1번에서 시간초과가 나서 그냥 queue로 바꿨다 ㅎㅎ..
pq는 insert할 때마다 logN의 시간이 소모되니 비효율적이였나보다

코드는 아래와 같다.

#include<vector>
#include<queue>

using namespace std;

typedef struct __pos {
    int row;
    int col;
    int cost;
} pos;

int rowDir[4] = { -1, 0, 1, 0 };
int colDir[4] = { 0, 1, 0, -1 };
int visit[101][101];

int solution(vector<vector<int> > maps)
{
    int answer = -1;
    int n = maps.size();
    int m = maps[0].size();
    
    queue<pos> q;
    q.push( {0, 0, 1} );
    
    while(1) {
        if(q.empty())
            break;
        
        pos cur = q.front(); q.pop();
        if(cur.row == n-1 && cur.col == m-1) {
            answer = cur.cost;
            break;
        }
        if(visit[cur.row][cur.col] == 1)
            continue;
        visit[cur.row][cur.col] = 1;
        
        for(int i=0;i<4;i++) {
            pos npos = { cur.row + rowDir[i], cur.col + colDir[i], cur.cost + 1 };
            
            if(npos.row < 0 || npos.row >= n || npos.col < 0 || npos.col >= m)
                continue;
            if(maps[npos.row][npos.col] == 0)
                continue;
            
            q.push(npos);
        }
    }
    
    return answer;
}