[ 프로그래머스 C++ ] 리코쳇 로봇 lv2

해설

어렸을 적에 자주 해봤을 법 한 미끄러지는 게임이다. BFS로 접근했다.

BFS와 동일하게 설계하되 이동은 Slide 함수로 하게 했다.

보드판을 새롭게 만들고 한번 방문했을 때의 count 값을 추가하여 count가 더 적을때만 갱신시켜주었다.

BFS폼은 동일하게 유지하되 새로운 조건을 추가한 문제. BFS를 자주 풀어봤다면 골치를 썩을만한 문제는 아닌것 같다.

 

G 상하좌우로 D가 없거나 G가 사이드에 붙어있지 않다면 G로는 어떻게 해서든 가지 못한다. 이 조건을 먼저 체크해주면 시간이 제법 줄어들지만 나는 귀찮아서 그렇게는 하지 않음.

---

문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.

위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

---

코드

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

using namespace std;
int defense[4][2] = { {-1,0},{0, -1},{1,0},{0,1} };

void Slide(pair<int, int> SlideDir, pair<int, int>& Position, 
           const vector<vector<pair<string, int>>>& Board, pair<int, int> BoardScale)
{
    while (true)
    {
        Position.first += SlideDir.first;
        Position.second += SlideDir.second;

        if (Position.second < 0 || Position.first < 0 || Position.second >= BoardScale.second ||
            Position.first >= BoardScale.first || Board[Position.first][Position.second].first == "D")
        {
            Position.first -= SlideDir.first;
            Position.second -= SlideDir.second;
            return;
        }
    }
}

int solution(vector<string> board) {
    vector<vector< pair<string, int> >> MoveCountBoard(100, vector<pair<string, int>>(100,{" ", -1}));
    pair<int, int> StartPoint;
    pair<int, int> EndPoint;

    for (int i = 0; i < board.size(); i++)
    {
        for (int k = 0; k < board[i].size(); k++)
        {
            if (board[i][k] == 'D')
                MoveCountBoard[i][k].first = board[i][k];
            else 
            {
                if (board[i][k] == 'R')
                    StartPoint = { i,k };
                if (board[i][k] == 'G')
                    EndPoint = { i,k };
                MoveCountBoard[i][k] = make_pair(board[i][k], 10000);
            }        
        }
    }

    queue<pair<int, int>> task;
    task.push(StartPoint);
    MoveCountBoard[StartPoint.first][StartPoint.second].second = 0;

    while (!task.empty())
    {
        pair<int, int> CurTask = task.front();
        task.pop();
        int MoveCount = MoveCountBoard[CurTask.first][CurTask.second].second;

        for (int i = 0; i < 4; i++)
        {
            int NextX = CurTask.first + defense[i][0];
            int NextY = CurTask.second + defense[i][1];

            if (NextY < 0 || NextX < 0 || NextY >= board[0].size() || NextX >= board.size()
                || MoveCountBoard[NextX][NextY].first == "D")
                continue;

            pair<int, int> NextPos = CurTask;
            Slide({ defense[i][0] , defense[i][1] }, NextPos, MoveCountBoard, { board.size(), board[0].size() });
            if(NextPos == EndPoint)
                return MoveCount + 1;
			else if (MoveCountBoard[NextPos.first][NextPos.second].second > (MoveCount + 1))
			{
				MoveCountBoard[NextPos.first][NextPos.second].second = MoveCount + 1;
				task.push(NextPos);
			}
        }
    }
    return -1;
}