[C++] 프로그래머스 문제풀이 LEVEL 2 리코쳇 로봇

 

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

프로그래머스

 

 

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

std::pair<int, int> move(std::vector<std::string> & board, int y, int x, int dir){
    const int dy[] = {-1, 1, 0, 0};
    const int dx[] = {0, 0, -1, 1};
    while(y >= 0 && y < board.size() && x >= 0 && x < board[y].size() && board[y][x] != 'D'){
        y += dy[dir];
        x += dx[dir];
    }
    return {y - dy[dir], x - dx[dir]};
}


int solve(std::vector<std::string> & board, int sy, int sx){
    
    std::queue<std::pair<int, int>> q;
    std::vector<std::vector<int>> dist(board.size(), std::vector<int>(board[0].size(), -1));

    q.push({sy, sx});
    dist[sy][sx] = 0;
    while(!q.empty()){
        auto [y, x] = q.front(); q.pop();
        for (int dir = 0; dir < 4; ++dir){
            auto [ny, nx] = move(board, y, x, dir);
            if (dist[ny][nx] != -1) continue;
            q.push({ny, nx});
            dist[ny][nx] = dist[y][x] + 1;
            if (board[ny][nx] == 'G'){
                return dist[ny][nx];
            }
        }
    }
    return -1;
}

int solution(vector<string> board) {
    int answer = 0;
    int sy, sx;
    for (int y = 0; y < board.size(); ++y){
        for (int x = 0; x < board[y].size(); ++x){
            if (board[y][x] == 'R'){
                sy = y;
                sx = x;
            }
        }
    }
    answer = solve(board, sy, sx);
    std::cout << answer << "\n";
    return answer;
}