프로그래머스 - 찾아라 프로그래밍 마에스터 게임 맵 최단거리

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

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

 

bfs 문제였다!

 

 

 

 

 

 

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

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

vector<vector<bool>> visited;

int bfs(const vector<vector<int>>& maps, vector<vector<bool>>& visited) {
    
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    
    int n = maps.size();
    int m = maps[0].size();
    
    int cnt = 0;
    while(!q.empty()) {
        int qSize = q.size();
        cnt++;
        for(int i = 0; i < qSize; i++) {
            int cy = q.front().first;
            int cx = q.front().second;
            q.pop();
            
            if(cy == n - 1 && cx == m - 1) return cnt;
            
            for(int dir = 0; dir < 4; dir++) {
                int ny = cy + dy[dir];
                int nx = cx + dx[dir];
                if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if(visited[ny][nx]) continue;
                if(!maps[ny][nx]) continue;
                visited[ny][nx] = true;
                q.push({ny, nx});
            }
            
        }
    }
    
    return -1;
}

int solution(vector<vector<int>> maps)
{
    int answer = 0;
    
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size(), false));
    
    answer = bfs(maps, visited);
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~