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

 

1. 현재의 위치를 큐에 넣는다
2. 큐에서 위치를 하나씩 빼서 
    1. 갈 수 있고
    2. 최소비용
    두가지 조건을 모두 만족하면 다시 큐에 집어넣는다
3. 큐에서 도착지점을 발견하게 되면 끝낸다

 

이 알고리즘으로 문제를 풀었다.

#include<vector>
#include <queue>

using namespace std;

/*
dfs로 풀어야할지 아니면 bfs로 풀어야할지 잘 모르겠다.
bfs로 풀자
별도로 배열을 두어서 거기까지 가게된 최소 단위를 저장해놓자.
1. 현재의 위치를 큐에 넣는다
2. 큐에서 위치를 하나씩 빼서 
    1. 갈 수 있고
    2. 최소비용
    두가지 조건을 모두 만족하면 다시 큐에 집어넣는다
3. 큐에서 도착지점을 발견하게 되면 끝낸다
*/
int visited[101][101];
int dx[4] = {1,-1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int solution(vector<vector<int> > maps)
{
    int n = maps.size();
    int m = maps[0].size();
    int answer = -1;
    queue<pair<int, int>> q;
    visited[0][0]=1;
    q.push({0, 0});
    while (!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        if (y==n-1 && x==m-1){
            answer = visited[y][x];
            break;
        }
        for (int i=0;i<4;i++){
            int ny = y+dy[i];
            int nx = x+dx[i];
            if (nx<0 || ny<0 || ny>=n || nx>=m){
                continue;
            }
            if (maps[ny][nx]==0){
                continue;
            }
            if (visited[ny][nx]==0){
                visited[ny][nx] = visited[y][x]+1;
                q.push({ny, nx});
            }
        }
        
    }
    return answer;
}