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

문제

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

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

풀이

BFS를 통해 문제를 해결할 수 있었다. 최단 거리 측정이 요구되기 때문에 dist배열을 만들어 각 칸의 도달하는 최단 스텝을 저장해주었다. 또한 문제에서 게임 맵의 행과 열이 주어지지 않기 때문에 따로 행과 열을 구해주었다.

BFS를 돌며 벽의 유/무를 확인해주고 dist배열을 통해 최단 거리 및 방문 여부(dist배열의 값이 -1이면 방문하지 않은 곳임)를 확인하고 맵의 맨 끝의 dist배열의 값을 구해주면 된다. 만약 맵의 맨 끝까지 도달할 수 없어 방문하지 못한다면 문제의 의도대로 -1이 나올 것이다. 

코드

#include<vector>
#include<queue>
#define x first
#define y second
using namespace std;

int n, m;
int result = 0;
int dist[101][101];
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0 , 1, 0, -1 };

void bfs(vector<vector<int>> maps)
{
    queue<pair<int, int>> q;

    q.push({ 0, 0 });
    dist[0][0] = 0;

    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();

        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1)
            {
                continue;
            }
            if (dist[nx][ny] != -1 || maps[nx][ny] == 0)
            {
                continue;
            }

            q.push({ nx, ny });
            dist[nx][ny] = dist[cur.x][cur.y] + 1;
        }
    }

}

int solution(vector<vector<int>> maps)
{
    int answer = 0;

    for (int i = 0; i < 101; i++)
    {
        for (int j = 0; j < 101; j++)
        {
            dist[i][j] = -1;
        }
    }

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

    bfs(maps);

    if (dist[n - 1][m - 1] != -1)
    {
        answer = dist[n - 1][m - 1] + 1;
    }
    else
    {
        answer = dist[n - 1][m - 1];
    }

    return answer;
}