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

 

BFS를 이용한 문제풀이입니다.

주어진 board에서 robot의 위치를 먼저 구합니다.

로봇은 상하좌우 방향으로 움직일 수 있고,

한 방향으로 움직이다가 장애물 D를 만나거나 board에 끝에 도달할때까지 움직입니다.

 

로봇이 움직일 수 있는 위치는 list큐에 넣습니다.

움직일 수 있는 위치 여부는 상하좌우(moves배열) 방향을 다 확인하고

한번 방문한 위치는 board를 C로 표기하여 중복 방문을 막습니다.

list 큐가 empty면 G에 도달하지 못한 것이므로 -1을 반환하고,

중간에 G에 도달하면 해당위치의 count를 반환합니다.

 

입출력 예#1의 로봇 움직임

 

 

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

using namespace std;

int solution(vector<string> board) {
    int answer = -1;
    pair<int, int> pos_robot;
    
    int rowN = board.size();
    int colN = board[0].size();
    
    for(int i=0; i<rowN; i++){
        for(int j=0; j<colN; j++){
            if(board[i][j] == 'R'){
                pos_robot = make_pair(i, j);
                break;
            }
        }
    }
    
    queue <pair<int,int>> list;
    queue <int> count;
    
    list.push(pos_robot);
    count.push(0);
    
    int moves[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    while(!list.empty()){
        int x = list.front().first;
        int y = list.front().second;
        int n = count.front();
        
        for(int i=0; i<4; i++){
            while(x+moves[i][0] >= 0 && x+ moves[i][0] < rowN && y+moves[i][1] >= 0 && y+moves[i][1]<colN && board[x+moves[i][0]][y+moves[i][1]] !='D'){
                x += moves[i][0];
                y += moves[i][1];
            }
        
        if(x != list.front().first || y != list.front().second){
            if(board[x][y] == 'G'){
                answer = n + 1;
                return answer;
            }
            if(board[x][y] != 'C'){
                list.push(make_pair(x,y));
                count.push(n+1);
                board[x][y] = 'C';
            }
            x = list.front().first;
            y = list.front().second;
        }
        }
        list.pop();
        count.pop();
    }
    return answer;
}

 

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