게임 맵 최단거리 1844

문제

접근 방법

DFS로도 가능할 것 같긴 하지만 BFS가 더 효율적인 것 같은 문제이다. 이미 방문한 길은 체크해두고 다음 길로 가면 되는 것이다.

코드

#include <vector>
#include <queue>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int solution(vector<vector<int>> maps)
{
    queue<pair<int, int>> bfs;
    bfs.push({0, 0});
    while (!bfs.empty())
    {
        auto cur = bfs.front();
        bfs.pop();
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> next = {cur.first + dy[i], cur.second + dx[i]};
            if (next.first < 0 | next.second < 0 | next.first >= maps.size() | next.second >= maps[next.first].size())
                continue;
            if (!maps[next.first][next.second] || maps[next.first][next.second] > 1)
                continue;
            if (next.first == maps.size() - 1 && next.second == maps[next.first].size() - 1)
            {
                return maps[cur.first][cur.second] + 1;
            }
            else
            {
                maps[next.first][next.second] = maps[cur.first][cur.second] + 1;
                bfs.push(next);
            }
        }
    }
    return -1;
}

풀이

기본적인 탐색 문제이다. 허용된 곳만 이동하게끔 작성하면 된다.
처음에는 구조체를 만들어 길이, 좌표를 저장했다가 수정하였다. 큰 차이는 없겠지만 구조체에 길이를 저장하여 쌓아두는 것보단 이미 있는 maps에 값을 바꾸는 편이 더 좋다고 생각해서 그렇게 했다. 큰 차이는 없었다.