Snakes and Ladders

정사각형 보드를 나타내는 2차원 정수 벡터 board를 받는다.

보드에는 가장 좌측 하단을 1로 시작하여 행의 극단으로 갈 수록 1씩 증가하는 인덱스가 매겨져 있다.

또한 행의 끝에 도달하면 동일한 열의 상위 행으로 올라가며 인덱스가 매겨진다.

가장 좌측 하단에서 시작하여 최상단 끝에 도달할때 가장 적은 이동 수를 구하는 문제이다.

특정 인덱스에서는 다른 인덱스로 점프를 할 수 있으며 가능할 경우

보드 벡터에 점프할 수 있는 인덱스가 쓰여져 있으며, -1은 점프가 불가능하다는 뜻이다.

또한 점프는 단방향으로만 작동한다.

이미지 출처

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        
        int n = board.size();

        vector<int> distance(n * n, -1);
        queue<int> waiting{};

        waiting.push(0);
        distance[0] = 0;

        int target{n * n - 1};
        while (waiting.empty() == false)
        {
            int index{waiting.front()};
            waiting.pop();
            
            for (int i = index + 1; i <= std::min(target, index + 6); ++i)
            {
                auto next = IndexToPosition(i, n);
                int nextIndex = board[next.first][next.second] != -1 ? board[next.first][next.second] - 1 : i;
                if (distance[nextIndex] == -1 || distance[index] + 1 < distance[nextIndex])
                {
                    distance[nextIndex] = distance[index] + 1;
                    waiting.push(nextIndex);
                }
            }
        }
        
        return distance[target];
    }

private:
    pair<int, int> IndexToPosition(int &index, int &n)
    {
        auto dv = div(index, n);

        pair<int, int> result{n - dv.quot - 1, dv.rem};
        if ((dv.quot % 2) == 1)
        {
            result.second = n - dv.rem - 1;
        }

        return result;
    }
};