[Programmers] 게임 맵 최단거리 (C++)

문제

상대 팀 진영에 도착하기 위해 지나가야 하는 칸의 최소 개수 찾기

도착할 수 없는 경우에는 -1 리턴

1은 지나갈 수 있는 곳, 0은 지나갈 수 없는 곳

생각할 것

최단거리를 구하는 것이므로 BFS 이용하기

코드

#include<vector>
#include<queue>
#include<iostream>
using namespace std;
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1};
int solution(vector<vector<int> > maps)
{
    int answer = -1;
    int n = maps.size();
    int m = maps[0].size();
    vector<vector<int>> visited(n, vector<int>(m));
    queue<pair<int,int>> q;
    
    // 상대 진영에서 시작
    q.push({n-1, m-1});
    visited[n-1][m-1] = 1;
    while(!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        
        if(cx == 0 && cy == 0) return visited[cx][cy];
        for(int k = 0; k < 4; k++){
            int nx = cx + dx[k];
            int ny = cy + dy[k];
            if(!(0 <= nx && nx < n && 0 <= ny && ny < m)) continue;
            if(visited[nx][ny] > 0) continue;         
            else {
                if(maps[nx][ny]) q.push({nx, ny});
                visited[nx][ny] = visited[cx][cy] + 1;
            }
        }
    }
    
    return answer;
}

상대진영에서 시작하지 않아도 된다