Programmers : 리코쳇 로봇

문제링크

풀이요약

BFS

풀이상세

1. 반복문을 통해, 임의의 백터 한 방향으로 쭉 직진한다.

2. 만약 벽을 만나거나 인덱스를 넘어가는 경우, 현재 사용한 백터 좌표 -1 의 값을 q에 반영한다.

3. 가장 빠른 길을 가는 경우는 길의 방향에 중복이 존재하지 않을 터이다. (계속 빙글빙글 도는 것 보다, 몇몇 최적 좌표만 찾아 가는게 당연히 더 빠를 수 밖에 없다.) 따라서, q가 반영되는 좌표에 대해 방문처리를 진행한다.

4. 처음 goal에 도달했을 때의 횟수가 가장 적게 움직인 횟수가 된다.

#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;
queue<pair<pair<int,int>, int>> q;
int dr[4] = {-1,0,1,0};
int dc[4] = {0,-1,0,1};
pair<int,int> goal;
int visited[104][104];

int solution(vector<string> board) {
    int answer = 0;    
    for(int i=0; i<board.size(); i++) {
        for(int j=0; j<board[i].size(); j++) {
            if(board[i][j]=='R') {
                q.push({{i,j},0});
            } else if(board[i][j] == 'G') {
                goal = {i,j};
            }
        }
    }
    
    while(!q.empty()) {
        pair<pair<int,int>,int> curr = q.front();
        q.pop();
        if(visited[curr.f.f][curr.f.s]) continue;
        visited[curr.f.f][curr.f.s]++;
        
        if(curr.f.f == goal.f && curr.f.s == goal.s) return curr.s;
        
        for(int d=0;d<4; d++) {
            int nr = curr.f.f;
            int nc = curr.f.s;
            
            while(true) {
                nr += dr[d];
                nc += dc[d];
                
                if(nr < 0 || nc < 0 || nr >= board.size() || nc >= board[0].size() || board[nr][nc] == 'D') {
                    nr -= dr[d];
                    nc -= dc[d];
                    q.push({{nr,nc},curr.s+1});
                    break;
                }
            }
        }
    }
    return -1;
}