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

문제 링크

게임 맵 최단거리

풀이

BFS/DFS로 푸는 문제. 난 BFS로 풀었다.

1. BFS는 queue로 풀어야 하기 때문에 현재 위치 (0,0)을 큐에 넣는다.
   1-1. 방문했는지 알기 위한 visit과 거리를 나타내는 dist에도 [0][0]값을 1로 갱신한다.
2. queue가 빌 때까지 반복하는데, 현재 위치 curX와 curY에서 상하좌우 값을 구해(nx, ny) 범위를 벗어나거나, 벽이거나, 방문했으면 continue 해준다.
   2-1. 아니라면 queue에 넣어주고, dist와 visit 값을 갱신한다.
3. dist[n-1][m-1] 값을 return 해주면 끝.

코드

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

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

vector<vector<int>> maps;

void BFS(int n, int m, vector<vector<int>> &dist)
{
    vector<vector<int>> visit(n,vector<int>(m));
    
    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    dist[0][0] = 1;
    visit[0][0] = 1;
    
    while(!q.empty())
    {
        int curX = q.front().second;
        int curY = q.front().first;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx = curX + dx[i];
            int ny = curY + dy[i];
            if(nx>=m || nx<0 || ny>=n || ny<0) continue;
            if(maps[ny][nx]==0) continue;
            if(visit[ny][nx]==1) continue;
            q.push(make_pair(ny,nx));
            dist[ny][nx] = dist[curY][curX]+1;
            visit[ny][nx] = 1;
        }
    }
}

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