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

문제 링크

리코쳇 로봇

풀이

BFS로 푸는 문제

1. 시작점 R을 구해 queue에 넣고 방문했는지 체크하는 visit과 해당 인덱스에 최소 이동 거리를 저장하는 depth를 초기화한다.
   1-1. depth는 min으로 구할거라 INF로 초기화해준다.
2. 위, 아래, 좌, 우 체크하는 dx, dy를 이용해 ny, nx를 계속 갱신해주는데, 해당 인덱스가 범위를 벗어나거나 벽(D)일 경우 바로 그 전 인덱스로 갱신하고 queue에 넣어준다. 방문 처리를 위한 visited[ny][nx]와 최소 이동 수 depth[ny][nx]도 갱신한다.
3. queue while문이 끝났다면 G의 인덱스를 찾아 depth를 return 한다.
   방문이 안되는 경우는 INF로 되어있으므로 -1을 return 한다.

코드

#include <string>
#include <vector>
#include <queue>
#define INF 100000

using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int BFS(vector<string> &board, int rowCnt, int colCnt, int rRow, int rCol)
{
    vector<vector<int>> visited(rowCnt, vector<int>(colCnt));
    vector<vector<int>> depth(rowCnt, vector<int>(colCnt,INF));
    queue<pair<int,int>> q;
    
    q.push({rRow, rCol});
    visited[rRow][rCol] = 1;
    depth[rRow][rCol] = 0;
    
    while(!q.empty())
    {
        int curRow = q.front().first;
        int curCol = q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            int ny = curRow;
            int nx = curCol;
            while(1)
            {
                ny += dy[i];
                nx += dx[i];
                if(ny<0 || ny>=rowCnt || nx<0 || nx>=colCnt) //범위 밖이면
                {
                    ny -= dy[i];
                    nx -= dx[i];
                    break;
                }
                if(board[ny][nx]=='D')
                {
                    ny -= dy[i];
                    nx -= dx[i];
                    break;
                }
            }
            if(visited[ny][nx]) continue;
            visited[ny][nx] = 1;
            depth[ny][nx] = min(depth[ny][nx], depth[curRow][curCol]+1);
            q.push({ny, nx});
        }
    }
    
    for(int i=0;i<depth.size();i++)
    {
        for(int j=0;j<depth[i].size();j++)
        {
            if(board[i][j]=='G')
            {
                if(depth[i][j]==INF) return -1;
                return depth[i][j];
            }
        }
    }
}

int solution(vector<string> board) {
    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[i].size();j++)
        {
            if(board[i][j]=='R')
            {
                return BFS(board, board.size(), board[i].size(), i, j);
            }
        }
    }

}