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

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

int solution(vector<vector<int>> maps)
{
    int answer = 0;
    int n = maps.size();
    int m = maps[0].size();
    bool visited[100][100] = { false };
    vector<pair<int, int>> direction = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    queue<pair<int, int>> node;

    node.push({ 0, 0 });
    visited[0][0] = true;

    while (!node.empty())
    {
        int value = maps[node.front().first][node.front().second];

        for (int i = 0; i < direction.size(); i++)
        {
            int x = node.front().first + direction[i].first;
            int y = node.front().second + direction[i].second;

            if (n <= x || m <= y || 0 > x || 0 > y)
                continue;
            if (maps[x][y] == 0)
                continue;
            if (visited[x][y])
                continue;

            node.push({ x, y });
            maps[x][y] += value;
            visited[x][y] = true;
        }

        node.pop();
    }

    if (maps[n - 1][m - 1] == 1)
        return -1;

    answer = maps[n - 1][m - 1];

    return answer;
}

풀이

1. 현재 위치에서 상하좌우의 위치들을 넣어준다. 이 때 벽이거나 도달했던 곳은 방문하지 않는다.

2. 먼저 도달한 순으로 queue에 들어가므로 해당 위치에 제일 최적의 거리가 나온다.

3. 도착할 위치가 1이면 도달하지 못했으므로 -1을 리턴해준다.

 

 

헤매었던 점

- 끝 지점의 왼쪽과 위쪽이 벽일 경우 가지않아도 되므로 처음에 계산하기 전에 -1을 적용해주었는데 오류가 났었다.

if (maps[maps.size() - 2][maps[0].size() - 1] == 0 
        && maps[maps.size() - 1][maps[0].size() - 2] == 0)
        return -1;

n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

이 부분을 보고 세로로 1칸이나 가로로 1칸이 있을 수도 있겠다라는 생각을 하였다.

저것을 지워버리고 마지막칸이 1일 때로 하니 해결되었다.

 

 

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

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