[Lv 2] 리코쳇 로봇

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

프로그래머스

 

이 문제는 BFS를 사용하는 문제이다.

알고리즘은 다음과 같다. 

1. 처음 위치와 끝 위치를 알기위해 board 배열을 순회한다.

2. bfs를 시작하기 전 queue에 시작 위치의 y좌표와 x좌표와 counter를 삽입한다.

3. 방문 배열의 y, x 좌표를 방문했다고 표시한다.

4. y좌표와 x좌표가 목적기 좌표인 경우 answer와 counter 중 최소인 값을 저장한다.

5. dx와 dy 배열을 통해 상하좌우 중 하나를 선택해서 'D'를 만날 때 까지 전진한다.

6. 만약 'D'를 만나는 경우 뒤로 한칸 이동한다.

7. 더이상 앞으로 전진할 수 없는 경우 현재 좌표가 방문한적 있는 좌표인지 확인 후 방문하지 않았다면 queue에 현재 좌표와 counter를 삽입한다.

 

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

using namespace std;
pair<int, int> start;
pair<int, int> goal;
int y, x, answer = 987654321;
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
bool visited[100][100];

void bfs(vector<string> &board) {
    queue<pair<pair<int, int>, int>> q;
    
    q.push({{start.first, start.second}, 0});
    visited[start.first][start.second] = true;
    
    while (!q.empty()) {
        int cy = q.front().first.first;
        int cx = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
        
        if (cy == goal.first && cx == goal.second) {
            answer = min(answer, cnt);
        }
        
        for (int i=0; i<4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            
            if ((ny < 0 || y <= ny || nx < 0 || x <= nx) || board[ny][nx] == 'D') continue;
            
            while (true) {
                ny += dy[i];
                nx += dx[i];
                
                if ((ny < 0 || y <= ny || nx < 0 || x <= nx) || board[ny][nx] == 'D') {
                    ny -= dy[i];
                    nx -= dx[i];
                    break;
                }
            }
           
            if (visited[ny][nx]) continue;
            
            q.push({{ny, nx}, cnt + 1});
            visited[ny][nx] = true;
        }
    }
}

int solution(vector<string> board) {
    answer = 987654321;
    
    y = board.size();
    x = board[0].size();
    
    int counter = 0;
    for(int i = 0;i<y;i++){
        for(int j = 0;j<x;j++){
            if(counter == 2) break;
            
            if(board[i][j] == 'R'){
                counter++;
                start = {i, j};
            }
            else if(board[i][j] == 'G'){
                counter++;
                goal = {i,j};
            }
        }
    }
    bfs(board);
    if(answer == 987654321)
        return -1;
    
    return answer;
}