[알고리즘/C++] 프로그래머스 - 리코쳇 로봇 (Lv.2, BFS)

✏️ 풀이 방법

• bool 형으로 체크하는 방문 배열을 사용해서 방문한 모든 노드를 체크하려고 했는데
  풀면서 생각해보니 굳이 그럴 필요가 없었다.
  벽이나 장애물에 부딪히기 전까지는 직진만 하기 때문에
  해당 좌표에 몇번 방향 전환을 해서 도착했는지만 알고있으면 된다.
• 아래 코드로 제출해서 정답은 나왔지만 하나 의문인 점이 있는데,
  최소값을 계산하지 않아도 정답 처리가 됐다.
  오히려 min으로 비교를 했더니 이상한 값이 나오던데..
  👉 어차피 시작점을 기준으로 출발하기 때문에 먼저 해당 좌표에 도착했다면
  카운트가 INT_MIN에서 증가했을것이다. 이후 재방문했을시에는 무조건 먼저 방문했을때의 횟수보다 큰 값이기 때문에 재방문 처리만 해도 최소값 처리가 이루어진다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<string> board)
{
    vector<pair<int, int>> dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
    vector<vector<int>> moveCnt(board.size(), vector<int>(board[0].size(), INT32_MIN));

    pair<int, int> start = {-1, -1};
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[0].size(); ++j)
        {
            if (board[i][j] == 'R')
            {
                start = {i, j};
                break;
            }
        }
        
        if (start.first != -1)  break;
    }

    queue<pair<int, int>> waiting;
    waiting.push(start);
    moveCnt[start.first][start.second] = 0;

    while (waiting.empty() == false)
    {
        pair<int, int> curr = waiting.front();
        waiting.pop();

        for (int d = 0; d < dir.size(); ++d)
        {
            pair<int, int> next = {curr.first + dir[d].first, curr.second + dir[d].second};

            while (true)
            {
                if (next.first < 0 || next.first >= board.size() || next.second < 0 || next.second >= board[0].size())
                    break;

                if (board[next.first][next.second] == 'D')
                    break;

                next = {next.first + dir[d].first, next.second + dir[d].second};
            }

            next = {next.first - dir[d].first, next.second - dir[d].second};
            if (board[next.first][next.second] == 'G')
            {
                return moveCnt[curr.first][curr.second] + 1;
            }

            if (moveCnt[next.first][next.second] >= 0)
                continue;

            moveCnt[next.first][next.second] = moveCnt[curr.first][curr.second] + 1;
            
            waiting.push({next.first, next.second});
        }
    }

    return -1;
}