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

 

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

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

 

BFS를 이용해 맵의 최단 거리를 구하는 문제.

상하좌우를 이동하는데 조건을 검사하면서 진행하면 된다.

이동하려는 좌표가 벽이 아니고, 맵의 크기를 벗어나지 않으며 방문하지 않은 곳을 큐에 넣어준다.

만약 다음 좌표가 목적지라면 바로 리턴하여 최단 거리를 구한다.

큐가 빌 때까지 목적지에 도착 못하는 경우는 갈 수 없는 경우이기 때문에 while문을 탈출해 -1을 리턴.

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

using namespace std;

int solution(vector<vector<int>> maps)
{
    int answer = 1;
    int n = maps.size();
    int m = maps[0].size();
    int goalX = n - 1, goalY = m - 1;
    int directX[4] = {-1, 1, 0, 0};
    int directY[4] = {0, 0, -1, 1};
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    
    q.push(make_pair(0, 0));
    visited[0][0] = true;
    
    while(!q.empty()){
        int size = q.size();
        
        for(int i = 0; i < size; i++){
            int x = q.front().first;
            int y = q.front().second;
            
            q.pop();
                        
            for(int j = 0; j < 4; j++){
                int nextX = x + directX[j];
                int nextY = y + directY[j];
                
                if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && maps[nextX][nextY] != 0 && !visited[nextX][nextY]){
                    if(nextX == goalX && nextY == goalY){
                        return answer + 1;
                    }
                    q.push(make_pair(nextX, nextY));
                    visited[nextX][nextY] = true;
                }
            }
        }
        answer++;
    }
    
    return -1;
}