[Programmers/Level2] 프로그래머스 - 리코쳇 로봇 [C++ 풀이]

 

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

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

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

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

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

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

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

 

최소 이동 횟수를 구하는 격자 문제이다.
기존 BFS처럼 한 칸의 이동이 1회가 아니라 기존 위치에서 쭈우우우욱 미끄러져서 벽 혹은 장애물에 닿을 때 횟수를 1 카운팅한다고 한다.

 

시작위치 R에서 목표 G로 도달할 수 있는 최소 이동 횟수를 구하는 문제, 도달할 수 없다면 -1을 출력한다.

 

큐에 넣는 조건

1. 방문 안 한 위치인 경우

2. 이미 방문을 했다면 이번 방문 횟수가 기존 방문 횟수보다 적을 경우.

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool visitedAt[101][101];
int Dist[101][101];

bool IsValid(vector <vector<char>>& tile, int nX, int nY){
    if(nX > -1 && nY > -1 && nX < tile.size() && nY < tile[0].size()){
        if(tile[nX][nY] != 'D'){
            return true;
        }
    }
    return false;
}

void bfs(vector <vector<char>>& tile, int startX, int startY){
    pair <int, int> origin;
    queue <pair <int, int>> que;
    que.push({startX, startY});
    visitedAt[startX][startY] = true;
    
    while(!que.empty()){
        origin = que.front(); que.pop();
        
        for(int i = 0; i < 4; i++){
            pair <int, int> temp = origin;
            while(true){
                int nX = dx[i] + temp.first;
                int nY = dy[i] + temp.second;
                
                if(!IsValid(tile, nX, nY))
                    break;
                
                temp.first = nX;
                temp.second = nY;
            }
            // 벽 or 장애물에 부딪혀서 한 번의 이동이 완료되었음
            
            // 현재 위치에 도달한 적이 없다면 Dist 갱신 후 큐에 넣어준다. 
            // -> (해당 위치부터 다시 시작 할거임)
            if(visitedAt[temp.first][temp.second] == false){
                Dist[temp.first][temp.second] = Dist[origin.first][origin.second] + 1;
                que.push({temp.first, temp.second});
                visitedAt[temp.first][temp.second] = true;
            }
            // 현재 위치에 도달한 적이 있다면, Dist를 확인한다. 짧다면 갱신해준다.
            else{
                if(Dist[temp.first][temp.second] > Dist[origin.first][origin.second] + 1){
                    Dist[temp.first][temp.second] = Dist[origin.first][origin.second] + 1;
                    que.push({temp.first, temp.second});
                }
            }
        }
    }
}

int solution(vector<string> board) {
    int answer = -1;
    vector <vector <char>> tile(board.size());
    
    int startX = 0, startY = 0;
    
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[0].size(); j++){
            tile[i].push_back(board[i][j]);
            if(board[i][j] == 'R'){
                startX = i;
                startY = j;
            }
        }
    }
    
    bfs(tile, startX , startY);
    
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[0].size(); j++){
            if(board[i][j] == 'G')
                answer = Dist[i][j] != 0 ? Dist[i][j] : -1;
        }
    }
    
    
    return answer;
}