프로그래머스 리코쳇 로봇

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

프로그래머스

 

문제 접근법: bfs문제입니다.

난이도는 쉬우니 딱히 크게 얘기는 하지 않겠고 이동할때 벽을부딪힐때까지만 이동해서 G를 이동만하면되는 문제입니다.

 

소스코드 :

#include <bits/stdc++.h>

using namespace std;

int n,m;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
bool isrange(int y,int x){
    return 0<=y&&y<n&&0<=x&&x<m;
}
int bfs(vector<string> &board){
    vector<vector<int>>check(n,vector<int>(m));
    int cnt=0;
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(board[i][j]=='R'){
                q.push({i,j});
                check[i][j]=1;
            }
        }
    }

    while(!q.empty()){
        int qsize=q.size();
        while(qsize--){
            int y,x;
            tie(y,x)=q.front();
            q.pop();
            if(board[y][x]=='G')return cnt;
            for(int i=0;i<4;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                while(isrange(ny,nx)&&board[ny][nx]!='D'){
                    ny+=dy[i];
                    nx+=dx[i];
                }
                ny-=dy[i];
                nx-=dx[i];
                if(check[ny][nx]==0){
                    q.push({ny,nx});
                    check[ny][nx]=1;
                }
            }
        }
        cnt++;
    }
    return -1;
}
int solution(vector<string> board) {
    int answer = 0;
    n=board.size();
    m=board[0].size();
    return bfs(board);
}

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.