[Programmers] 리코쳇 로봇(Lv.2)

풀이 소요시간 : 40분(?)

문제를 제대로 안읽어서 다 풀고 처음부터 다시 풀었다. 한 칸씩 이동하는 것이 아니라 장애물이나 가장자리에 부딛힐 때 까지 미끄러져 이동하는 것이 포인트다. 미끄러져 이동하는 부분을 구현하는 것은 각자의 재량인 것 같은데, 다른 사람들의 풀이를 보니 다들 비슷한 것 같다.

전체 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int N, M;

char Map[100][100];
int Visit[100][100];

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

struct Position {
    int x;
    int y;
    int time;
};


int Bfs(int x, int y) {
    
    //초기 값
    queue<Position> Q;
    Q.push({x, y, 0});
    
    while(!Q.empty()) {
        
        int px = Q.front().x;
        int py = Q.front().y;
        int time = Q.front().time;
        Q.pop();
        
        if(Map[px][py] == 'G') return time;
        
        for(int i = 0; i < 4; i++) {
            
            int nx = px;
            int ny = py;
            
            while(true) {
                
                if(nx + dx[i] == -1 || nx + dx[i] == N) break;
                if(ny + dy[i] == -1 || ny + dy[i] == M) break;
                if(Map[nx + dx[i]][ny + dy[i]] == 'D') break;
                
                nx += dx[i];
                ny += dy[i];
                
            }
            
            if(Visit[nx][ny] == 0) {
                Visit[nx][ny] = 1;
                Q.push({nx, ny, time + 1});
            }
        
        }
        
        
    }
    // 도달 불가능
    return -1;
}



int solution(vector<string> board) {
    
    int Ans = 0;
    
    N = board.size(); // 세로
    M = board[0].length(); // 가로
    
    // Map 채우기
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            Map[i][j] = board[i][j];
        }
    } 
    
    // 최단경로 구하기
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(Map[i][j] == 'R') {
                Visit[i][j] = 1;
                Ans = Bfs(i, j);
            }
        }
    } 
    
    // 결과 값 반환
    return Ans;
   
}