Level 2. 리코쳇 로봇

Level 2. 리코쳇 로봇

 

 

최단 거리를 구해야 하는 전형적인 BFS 문제다.

 

로봇을 이동시키는 것 외에 크게 번거로운 것은 없었고, 범위 검사는 unsigned 형을 사용하면 더 간편하게 할 수 있다.

 

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

using namespace std;

struct Point
{
    unsigned r;
    unsigned c;
    int dist;
};

enum class DIR
{
    UP,
    DOWN,
    LEFT,
    RIGHT
};

Point moveTo(Point& p, DIR dir, vector<string>& board)
{
    size_t R = board.size(), C = board.front().size();
    Point pM(p);
    int dr, dc;
    
    switch (dir)
    {
    case DIR::UP:    dr = -1; dc = 0; break;
    case DIR::DOWN:  dr = +1; dc = 0; break;
    case DIR::LEFT:  dr = 0; dc = -1; break;
    case DIR::RIGHT: dr = 0; dc = +1; break;
    }

    while ((pM.r + dr) < R && (pM.c + dc) < C && board[pM.r + dr][pM.c + dc] != 'D')
        pM.r += dr, pM.c += dc;

    ++pM.dist;

    return pM;
}

int solution(vector<string> board)    
{
    size_t R = board.size(), C = board.front().size();
    vector<vector<bool>> visited(R, vector<bool>(C, false));
    queue<Point> que;

    for (unsigned r = 0; r < R; ++r)
    {
        for (unsigned c = 0; c < C; ++c)
        {
            if (board[r][c] == 'R')
            {
                que.push({r, c, 0});

                break;
            }
        }
    }

    while (!que.empty())
    {
        Point p = que.front(); que.pop();

        if (board[p.r][p.c] == 'G')
            return p.dist;
        else if (visited[p.r][p.c])
            continue;

        visited[p.r][p.c] = true;

        que.emplace(moveTo(p, DIR::UP, board));
        que.emplace(moveTo(p, DIR::DOWN, board));
        que.emplace(moveTo(p, DIR::LEFT, board));
        que.emplace(moveTo(p, DIR::RIGHT, board));
    }

    return -1;
}