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

---

🔗 문제

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

프로그래머스

 

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

struct position{
    int x;
    int y;
    int count;
};

int solution(vector<string> board) {
    int answer = -1;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int row = board.size();
    int column = board[0].size();
    
    queue<position> q;
    vector<vector<bool>> visited(row, vector<bool>(column, false));
    
    for(int r=0; r<row; r++){
        for(int c=0; c<column; c++){
            if(board[r][c] == 'R'){
                q.push({r, c, 0});
                visited[r][c] = true;
                
                break;
            }
        }
    }
    
    while(!q.empty()){
        position p = q.front();
        q.pop();
        
        if(board[p.x][p.y] == 'G'){
            return p.count;
        }
        
        for(int i=0; i<4; i++){
            int nx = p.x;
            int ny = p.y;
            
            while (nx + dx[i] >= 0 && nx + dx[i] < row &&
                   ny + dy[i] >= 0 && ny + dy[i] < column &&
                   board[nx + dx[i]][ny + dy[i]] != 'D') {
                nx += dx[i];
                ny += dy[i];
            }
            
            if(!visited[nx][ny]){
                q.push({nx, ny, p.count + 1});
                visited[nx][ny] = true;
            }
        }
    }
    
    return answer;
}

---

📝 풀이

queue를 이용한 BFS를 사용하여 문제를 풀었습니다.

시작 위치 'R'를 board에서 찾아 q와 visited에 초기화합니다.

 

반복문을 q가 비어있지 않을 동안 실행합니다.

만약 q의 position 중 도착 위치 'G'에 도달했다면 count를 return해줍니다.

시작 위치부터 네 방향을 각각 이동합니다.

이동할 때 주의할 점은 한 방향으로 최대한 갈 수 있는 만큼, 즉 'D'를 만나기 전까지 이동합니다.

이동한 위치가 방문된 적이 없다면 q에 추가하고 visited에 방문 여부를 true로 갱신합니다.

 

반복문이 도중 count를 return 하지 않았다면 도달할 수 없으므로 -1를 return합니다.