프로그래머스 리코쳇 로봇 C++

 

처음엔 문제를 스스로 어렵게 만들어 생각하고 있었다.

되게 간단한 문제다.

 

일반적인 bfs 문제에서 '상', '하', '좌', '우' 로 한칸씩 움직이는 것이 아니라, 쭈우우욱 움직이는 것으로만 생각해서 풀면 된다.

나머지는 똑같다.

 

근데 처음엔 스스로 문제를 어렵게 만들어 생각하고 있었다. 하마터면 빠져들 뻔 했다.

잘 나와서 다행!

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

using namespace std;

// 우 좌 하 상 - 순서는 의미없음
int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

int visit[100][100]; // 방문 여부이자 depth

int n, m;
int startX, startY;
int endX, endY;
    

int bfs(int x, int y, vector<string>& board) {
 
    queue<pair<int, int>> que;
    que.push({x, y});
    visit[x][y] = 1;
    
    
    while(!que.empty()) {
        
        pair<int, int> top = que.front();
        
        int x = top.first;
        int y = top.second;
        
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            
            int tx = x;
            int ty = y;
            
            while(true) {
                
                if(tx + mx[i] < 0 || tx + mx[i] >= n || ty + my[i] < 0 || ty + my[i] >= m || board[tx + mx[i]][ty + my[i]] == 'D')
                    break;
                else {
                    tx += mx[i];
                    ty += my[i];
                }
                
            }
            
            if(visit[tx][ty] == 0) {
                
                visit[tx][ty] = visit[x][y] + 1;
                que.push({tx, ty});
                
                if(board[tx][ty] == 'G')
                    return visit[tx][ty];
                
            }
            
        }
        
        
    }
    return 0;
    
    
}

int solution(vector<string> board) {
    int answer = 0;
    
    n = board.size();
    m = board[0].length();
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(board[i][j] == 'R') {
                startX = i; startY = j;
            } else if(board[i][j] == 'G') {
                endX = i; endY = j;
            }
        }
    }
    
    
    
    return bfs(startX, startY, board) - 1;
}