[프로그래머스 2레벨 ] 리코쳇 로봇 (C++)

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

using namespace std;

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

int solution(vector<string> board) {
    int answer = -1;
    
    queue<pair<int, int>>q;
    for(int i=0; i<board.size(); i++)
    {
        for(int j=0; j<board[0].size(); j++)
        {
            if(board[i][j] == 'R') //시작점
            {
                q.push({i, j});
                visited[i][j] = 1;
            }
        }
    }
    
    while(!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();
        
        for(int i=0; i<4; i++)
        {    
            int ny = y;
            int nx = x;
            while(1) //가장자리나 장애물에 부딪힐 때까지   
            {
                ny += dy[i];
                nx += dx[i];
                if(nx < 0 || ny < 0 || nx >= board[0].size() || ny >= board.size()) break; //범위 밖
                if(board[ny][nx] == 'D') break; //장애물
            }
            
            ny -= dy[i]; //부딪히기 바로 전으로
            nx -= dx[i];
            if(visited[ny][nx]) continue; //방문 체크
            if(board[ny][nx] == 'G') answer = visited[y][x]; //도착점 
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    
    
    return answer;
}

 

bfs를 살짝 응용한 문제이다.

시작점을 저장하고 방문 배열을 사용한 것까지는 동일하다.

 

4방향을 탐색하면서 문제에 주어진 조건에 따라 장애물이나 가장자리에 도달할 때까지 이동하는 것을 1번으로 친다.

따라서 while 반복문을 통해 범위 및 장애물을 체크하면서 누적하여 좌표 값을 더해준다.

다만 이렇게 저장된 값은 범위 밖 및 장애물에 도달한 값이므로 한 칸만 빼주어야 한다.

 

이렇게 이동한 것을 1칸으로, 방문 체크와 목표에 도달했는지 체크한다.

이때 방문 배열을 방문 체크 겸, 좌표 값 저장을 해주므로 이를 통해 정답을 체크한다.

이때 주의할 것은 방문 배열의 값을 1로 시작했기에 최종 횟수에서는 1을 차감해야한다.

해당 코드에서는 ny, nx를 통해 목표를 체크하므로 1을 빼줄 필요 없이 현재 좌표 y, x의 값을 넣어주게 된다.