[Programmers] 리코쳇 로봇

리코쳇 로봇

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.
게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

풀이

먼저 board에서 R의 위치를 찾고 큐에 시작 위치를 넣었다.
while문에서 G을 만나면 종료 조건을 주고, 최소 이동을 구해야 해서 처음으로 G을 만나면 종료하면 된다.
종료 조건이 아니면, 큐에서 하나씩 꺼내어 상하좌우로 탐색하며 벽이나 장애물을 만날때까지 이동하고 해당 위치에서 x-1, y-1 을 했다.

하지만, 이동횟수를 다른 변수(visited)에 저장할 생각을 못했다.

코드

#include <bits/stdc++.h>

using namespace std;

int visited[101][101];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n,m;
int solution(vector<string> board) {
    n = board.size();
    m = board[0].size();
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if (board[i][j]=='R'){
                visited[i][j]=1;
                q.push({i,j}); // start
                break;
            }
    
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int x=cur.first, y=cur.second;
        if(board[x][y]=='G') // 종료 조건
            return visited[x][y]-1;
        
        for(int k=0; k<4; k++){
            int nx=x+dx[k], ny=y+dy[k];
            // 벽이나 장애물이 아니면
            while(nx>=0 && nx<n && ny>=0 && ny<m 
                  && board[nx][ny]!='D'){
                nx+=dx[k]; 
                ny+=dy[k];
            }
            // 벽이나 장애물 만나기 직전으로 이동
            nx-=dx[k]; 
            ny-=dy[k];
            if(visited[nx][ny]==0){
                visited[nx][ny] = visited[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    return -1; // 종료 조건을 만나지 못하면
}

정리

참고