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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

 

메모

- bfs 방법으로 풀이

- vector<vector<int>> maps의 n, m 값 구하는 코드는 다음과 같음

  int n = maps.size();

  int m = maps.[0].size();

- maps의 값이 1 이하인 경우 방문하지 못한 것으로 판별해 -1 return

 

맞힌 코드

#include <bits/stdc++.h>
using namespace std;

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