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

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

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

전형적인 BFS 문제였습니다.

 

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

int N, M;
vector<vector<int> > Maps;
bool visit[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct Info {
    int x, y, t;
};

int BFS() {
    queue<Info> q;
    q.push({ 0, 0, 1 });
    visit[0][0] = true;
    
    while(!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int t = q.front().t;
        q.pop();
        
        if(x == N - 1 && y == M - 1) return t;
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(visit[nx][ny] || Maps[nx][ny] == 0) continue;
            q.push({ nx, ny, t + 1 });
            visit[nx][ny] = true;
        }
    }
    
    return -1;
    
}

int solution(vector<vector<int> > maps)
{
    Maps = maps;
    N = maps.size();
    M = maps[0].size();
    
    return BFS();
}