문제 설명

문제 : 리코쳇 로봇
난이도 : Level 2

처음 문제를 읽었을 때 꼼꼼하게 읽지 않아서 문제 이해에 시간이 걸렸다..

시작 위치는 R이고 도착 위치는 G이다. 상,하,좌,우 4방향으로 움직인다는 조건을 보고 BFS/DFS로 풀어야겠다고 생각했다.

이 문제에서 핵심인 말의 움직임은 다음과 같다.

상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

즉, 장애물 D를 만나거나 벽을 만날때까지 미끄러져 이동한다했기 때문에 이 문제에서 한번 이동은 한 방향으로 쭉~~~ 이동시키고 벽이나 장애물을 만났을 때 멈추는 것을 의미하고, 그때 그 자리가 G라면 목표 위치에 도달한 것이다.

문제 해결 방법

BFS 알고리즘 사용

R을 찾는다

	for(int i=0; i<board.size(); i++){
        for(int j=0; j<board[i].size(); j++){
            if(board[i][j] == 'R') {
                q.push({i,j});
                dist[i][j] = 1;
            }
        }
    }

방향 별로 미끄러진다!

		for(int dir=0; dir<4; dir++){
            int nx = cur.X;
            int ny = cur.Y;
            while(1) {
                nx += dx[dir];
                ny += dy[dir];
                if(nx < 0 || ny < 0 || nx >= m || ny >= n) {
                    nx -= dx[dir];
                    ny -= dy[dir];
                    break;
                }
                if(0 <= nx && nx < m && 0 <= ny && ny < n && board[ny][nx] == 'D'){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    break;
                }
                
            }
            if(dist[ny][nx] == 0){
                dist[ny][nx] = dist[cur.Y][cur.X] + 1;
                q.push({ny,nx});
            }
        }

G를 만나면 그만 알아보자.

	while(!q.empty()) {
        auto cur = q.front(); q.pop();
        if(board[cur.Y][cur.X] == 'G'){
            return dist[cur.Y][cur.X] - 1;
        }
       ...
       ...
       ...
       ...
    }

다 확인해도 G에 갈 수 없으면 -1을 리턴한다.

전체 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define Y first
#define X second
using namespace std;

queue<pair<int,int>> q;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int n,m;
int ret;
int dist[104][104];
int solution(vector<string> board) {
    
    // init
    n = board.size();
    m = board[0].size();
    
    for(int i=0; i<board.size(); i++){
        for(int j=0; j<board[i].size(); j++){
            if(board[i][j] == 'R') {
                q.push({i,j});
                dist[i][j] = 1;
            }
        }
    }
    
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        if(board[cur.Y][cur.X] == 'G'){
            return dist[cur.Y][cur.X] - 1;
        }
        for(int dir=0; dir<4; dir++){
            int nx = cur.X;
            int ny = cur.Y;
            while(1) {
                nx += dx[dir];
                ny += dy[dir];
                if(nx < 0 || ny < 0 || nx >= m || ny >= n) {
                    nx -= dx[dir];
                    ny -= dy[dir];
                    break;
                }
                if(0 <= nx && nx < m && 0 <= ny && ny < n && board[ny][nx] == 'D'){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    break;
                }
                
            }
            if(dist[ny][nx] == 0){
                dist[ny][nx] = dist[cur.Y][cur.X] + 1;
                q.push({ny,nx});
            }
        }
    }
    return -1;
}