[프로그래머스] 리코쳇 로봇 (C++)

문제

프로그래머스

 

풀이

포켓몬스터 골드 얼음 동굴

 

이 문제는 포켓몬스터 골드버전 얼음 동굴 퍼즐과 동일한 매커니즘을 가진 문제다.

 

리코쳇 로봇은 상하좌우로 움직일 수 있고, 한 방향으로 움직일 시, 벽에 닿을 때까지 계속 해당 방향으로 움직인다.

이때, R에서 로봇이 출발 할 때, G에 도착하는 최소 이동 횟수를 반환하는 문제이다.

 

난 BFS를 이용하여 해당 문제를 풀이했다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int map[101][101];
bool visited[101][101];
int n,m;
pair<int,int> startPos;
pair<int, int> endPos;

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

void Init(vector<string> board){ // 정수형 맵으로 초기화
    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] !='D')
            {
                  map[i][j] = 0;
                if(board[i][j] =='G'){
                    endPos = {i, j};
                }
                else if(board[i][j] =='R'){
                    startPos = {i, j};
                    visited[i][j] = true;
                }
            }
            else{
                map[i][j] = -1;
            }
        }
    }
}

bool cmp(int moveX, int moveY){ // 이동을 멈춰야 하는 지 Bool 값을 반환하는 함수
    return moveX < 0 || moveY < 0 || moveX >= m || moveY >= n || map[moveY][moveX] == -1;
}

int BFS(){ // BFS
    queue<pair<int,int>> q;
    q.push(startPos);
    
    while (!q.empty()){ // 시작
        int yPos = q.front().first;
        int xPos = q.front().second;
        int moveValue =map[yPos][xPos] + 1;
        
        q.pop();
        
        for(int i = 0; i < 4; i ++){
            int moveY = yPos + dy[i];
            int moveX = xPos + dx[i];
                 
            if(cmp(moveX, moveY)) // 이동 불가 시 Continue
                continue;
            
            while(true){ // 이동 가능할 시, 계속 이동
                moveY += dy[i];
                moveX += dx[i];
                
                if( cmp(moveX, moveY) ){ // 멈췄을 때 Break
                    int stopY =  moveY - dy[i];
                    int stopX =   moveX - dx[i];
                    
                    // 현재 이동 거리가 더 작다면 큐에 저장하여 다시 이동
                    if(map[stopY][stopX] == 0 ||  map[stopY][stopX] > moveValue){
                        q.push({stopY, stopX});
                        map[stopY][stopX] = moveValue;   
                    }
                     break;
                }
            }
        }
    }
    
    int goal = map[endPos.first][endPos.second];
    return goal == 0 ? -1 : goal;
}

int solution(vector<string> board) {
    Init(board);
    return BFS();
}