[프로그래머스] 게임 맵 최단거리 (C++)

🍒문제

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

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

🍒풀이

1. Queue를 사용하여 BFS로 구현 -> 최단거리 조건

2. dist 배열을 사용하여 지나온 거리 중 최단거리 갱신

3. 마지막 좌표 (n,m)에 도달하였다면 dist[n][m] 값 리턴

4. 마지막 좌표에 도달하지 못 하면 -1 리턴

 

🍒코드

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
/*
(1,1) -> (n,m) 최단 거리 리턴
도착 못 할 경우 -1 반환
*/
int dir[4][2] = { {0,1}, {1,0}, {-1,0}, {0,-1}};
int dist[101][101]; //방문거리 표시

int solution(vector<vector<int> > maps)
{
    int answer = 9999;
    int n = maps.size(); //세로, 행
    int m = maps[0].size(); //가로, 열
    queue<pair<int, int>> q;
    memset(dist, -1, sizeof(dist));
    
    q.push({0,0});
    dist[0][0]=1;
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        if(y==n-1 && x == m-1)
            return dist[y][x];
        
        for(int i=0; i<4; i++){
            int ny = y + dir[i][0];
            int nx = x + dir[i][1];
            if(ny >=0 && ny < n && nx >=0 && nx < m){
                if(maps[ny][nx]==1 && dist[ny][nx]==-1){
                    dist[ny][nx] = dist[y][x]+1;
                    q.push({ny, nx});
                }
            }
        } 
    }

    return -1;
}