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

프로그래머스

 

 

• board 주고 최소 움직임 구해라 = bfs
• 한 칸씩 이동하는 것이 아닌 한 방향으로 장애물이나 보드의 끝에 부딫힐 때까지 이동
• "R"은 시작 위치, "D"는 장애물 위치, "G"는 목표 위치

 

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

using namespace std;

queue<pair<int, int>> q;
int dirX[4] = {1, -1, 0, 0};
int dirY[4] = {0, 0, 1, -1};
// 방문 여부 및 방문 시까지 몇 번 이동했는지 체크용
int dist[101][101];

int solution(vector<string> board) {
    int answer = 0;
    
    int height = board.size();
    int width = board[0].size();
    
    // 시작 위치 찾기
    for(int i = 0;i < height; i++) {
        for(int j = 0; j < width; j++) {
            if(board[i][j] == 'R') {
                q.push({i, j});
                dist[i][j] = 1;
            }
        }
    }
    
    // BFS
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        
        // 4방향으로
        for(int i = 0; i < 4; i++) {
            int nx = cur.second;
            int ny = cur.first;
            
            // 현재 좌표의 값이 G면 도착, 출발점부터 1이 있기 때문에 리턴 시 -1을 해줌
            if(board[cur.first][cur.second] == 'G')
            return dist[cur.first][cur.second] - 1;
            
            while(1) {
                nx += dirX[i];
                ny += dirY[i];
                
                // 보드의 끝 또는 장애물과 만나면 이동 종료
                if(nx < 0 || ny < 0 || nx >= width || ny >= height) {
                    nx -= dirX[i];
                    ny -= dirY[i];
                    break;
                }
                
                if(0 <= nx && nx < width && 0 <= ny && ny < height && board[ny][nx] == 'D'){
                    nx -= dirX[i];
                    ny -= dirY[i];
                    break;
                }
            }
            
            // 방문한 적 없으면 해당 좌표 방문까지 걸린 횟수 저장 및 출발점 갱신
            if(dist[ny][nx] == 0) {
                dist[ny][nx] = dist[cur.first][cur.second] + 1;
                q.push({ny, nx});
            }
        }
    }
    
    // 도착 못하면 -1 리턴
    return -1;
}