[프로그래머스 Lv.2] 리코쳇 로봇

[문제]

 

https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=cpp

프로그래머스

 

[풀이]

 

기본적인 구조는 DFS와 비슷하지만, 한 칸씩 이동하는 방식과 다르게 정해진 방향으로 쭉 이동해야합니다(인덱스 범위 내 or 다음 구역이 D가 아닌 경우). 이후 이동한 구역에 대해서는 현재까지의 이동 횟수(Count)를 기록합니다. 나중에 다시 돌아왔을 때 현재 Count보다 기록된 Count가 낮다면 해당 구역에서는 DFS를 다시 할 필요가 없기 때문입니다(이미 다른 구역을 모두 탐색한 곳이기 때문). 이런 식으로 이동하면서, 도달 가능한 방식을 찾고 그 중 가장 낮은 값을 리턴해줍니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
vector<vector<int>> Visited;
int LimitY = 0;
int LimitX = 0;
int CheckY[4] = {-1, 0, 1, 0};
int CheckX[4] = {0, 1, 0, -1};
int answer = INT32_MAX;
bool bIsFound = false;

void DFS(vector<string>& _board, int _StartY, int _StartX, int _Count)
{
    Visited[_StartY][_StartX] = _Count;

    // 위, 오른쪽, 아래, 왼쪽으로 진행 가능한지 체크
    // 진행이 불가능한 경우(이동 후 위치가 나와 동일한 경우)에는 실패 체크
    // 위에 반복
    for (size_t i = 0; i < 4; i++)
    {
        int TempY = _StartY;
        int TempX = _StartX;

        while (true)
        {
            TempY += CheckY[i];
            TempX += CheckX[i];

            if (TempY >= LimitY || TempY < 0 || TempX >= LimitX || TempX < 0) // 상하좌우가 이동 불가능한지 체크
            {
                TempY -= CheckY[i];
                TempX -= CheckX[i];
                break;
            }

            if (_board[TempY][TempX] == 'D')
            {
                TempY -= CheckY[i];
                TempX -= CheckX[i];
                break;
            }
        }

        if (Visited[TempY][TempX] <= _Count)
        {
            continue;
        }
        else if (_board[TempY][TempX] == 'G')
        {
            // 찾음
            bIsFound = true;
            answer = min(_Count, answer);
        }
        else
        {
            DFS(_board, TempY, TempX, _Count + 1);
        }
    }
}

int solution(vector<string> board) 
{
    int StartY = 0, StartX = 0;
    LimitY = board.size(); // 인덱스는 얘보다 -1 // 5
    LimitX = board[0].size(); // 인덱스는 얘보다 -1 // 7

    Visited.resize(board.size(), vector<int>(board[0].size(), INT32_MAX));

    // 원래 위치로 돌아오는 경우에는 폐기
    for (size_t y = 0; y < board.size(); y++)
    {
        for (size_t x = 0; x < board[y].size(); x++)
        {
            char CurDot = board[y][x];
            if ('R' == CurDot)
            {
                StartY = static_cast<int>(y);
                StartX = static_cast<int>(x);
            }
        }
    }

    int Count = 1;
    DFS(board, StartY, StartX, Count);

    if (bIsFound == false)
    {
        answer = -1;
    }

    return answer;
}