리코쳇 로봇(24분)

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

구현 아이디어 4분 구현 20분

풀이

최소 이동이기 때문에 BFS를 사용했다. 이미 갔던 블록이면 이전에 더 최소 이동으로 그 블록에 갈 수 있다는 뜻이기 때문에 이미 갔던 블록을 -1로 표시했다.

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

// 최소 이동. BFS.

using namespace std;

int map[100][100];

struct Robot
{
    int r, c, sum;
    Robot(int r, int c, int sum)
    {
        this->r = r;
        this->c = c;
        this->sum = sum;
    }
};

int solution(vector<string> board) {
    int answer = 0;
    
    int N = board.size();
    int M = board[0].size();
    
    // 큐에 로봇의 위치와 몇 번 이동했는지 담을 예정.
    queue<Robot> Q;
    
    // 골 위치.
    int goalr = 0, goalc = 0;
    
    // 보드 정보를 map 배열에 기록.
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            char c = board[i][j];
            if(c == 'D') map[i][j] = 1;
            else if(c == 'R')
            {
                // 이미 방문한 곳은 -1.
                map[i][j] = -1;
                Q.push(Robot(i, j, 0));
            }
            else if(c == 'G')
            {
                goalr = i;
                goalc = j;
            }
        }
    }
    
    int dr[4] = {-1, 0, 1, 0};
    int dc[4] = {0, 1, 0, -1};
    bool arrived = false;
    
    while(!Q.empty())
    {
        Robot robot = Q.front();
        Q.pop();
        
        if(robot.r == goalr && robot.c == goalc)
        {
            answer = robot.sum;
            arrived = true;
            break;
        }
        
        // 4방향 검사.
        for(int i = 0; i < 4; ++i)
        {
            int nextr = robot.r;
            int nextc = robot.c;
            
            while(true)
            {
                nextr += dr[i];
                nextc += dc[i];
                
                if(nextr < 0 || nextc < 0 || nextr >= N || nextc >= M || map[nextr][nextc] == 1)
                {
                    break;
                }
            }
            
            nextr -= dr[i];
            nextc -= dc[i];
            
            if(map[nextr][nextc] == -1) continue;
            else Q.push(Robot(nextr, nextc, robot.sum + 1));
            map[nextr][nextc] = -1;
        }
    }
    
    if(!arrived) answer = -1;
    
    return answer;
}