코딩테스트 -- 리코쳇 로봇 - (프로그래머스 / C++)

 

프로그래머스

문제!

---

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

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

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

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

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

 

---

요약하면

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

이러한 게임판을 주면 R 위치에서 G위치까지 이동시키는데 최단 이동횟수를 구하는 문제입니다.

여기서 좀 더 생각해주어야할 점은

1. 로봇은 한번 이동하면 끝까지 이동한다(벽에 닿을때 까지)

 

끝?

 

일반적인 탐색 문제인것 같습니다. 

최단 거리이기에 저는 각 횟수별 도착지점에 count를 저장해 주어 걸러주는 방법을 사용했습니다.

 

바로시작!

 

 

가장 먼저 기본적인 틀을 만들어 주어야합니다.

 

저는 아래같은 형식으로 틀을 만들어 주었습니다. 

 

(-1로 하니까 틀어 지네요....)

 

 

 

 

틀을 만드는 코드!

for(int i=0;i<board.size()+2;i++){  // 처리
        for(int j=0;j<board[0].size()+2;j++){
            if(i==0 || j==0 || i==board.size()+1 || j==board[0].size()+1){
                visit[i][j]=-1;
            }
            else{
                if(board[i-1][j-1]=='D'){
                    visit[i][j]=-1;
                }
                else if(board[i-1][j-1]=='R'){
                    
                    start[0]=i;
                    start[1]=j;
                }
                else if(board[i-1][j-1]=='G'){
                    target[0]=i;
                    target[1]=j;
                }
            }
        }
    }

테두리 및 장애물은 -1로 나머지는 0으로  그리고 시작점과 도착점을 찾아주었습니다.

 

 

 

그리고 바로 탐색 시작!

for(int i=0;i<4;i++){
        dfs(start[0],start[1],i,1);
    }

 

 

 

함수에서는 방향과 count 현재위치를 받아주고 

가장먼저 도착지점에 왔는지를 확인해줍시다.

void dfs(int now_y,int now_x,int dir,int count){ // 좌표와 방향
    if(now_y==target[0]&& now_x==target[1]){
        answer=min(answer,count-1);
        return;
    }
   
    if(answer<=count || visit[now_y][now_x]==-1){
        return;
    }

다음으로는 이동횟수가 현재 최단횟수보다 큰지와 현재위치가 장애물 위는 아닌지 체크해줍시다.

 

 

위의 조건을 지나면 이제는 방향에 따라 로봇을 쭉 보내줍시다. 

while(1){  /// 쭉 보내기
        move_y+=dy[dir];
        move_x+=dx[dir];
        if(visit[move_y][move_x]==-1){//길막힘 
            move_y-=dy[dir];
            move_x-=dx[dir];//멈추기
            break;
        }
    }

길이 막혔으면 한칸뒤로!

 

 

그리고 마지막으로 지금 count와 그칸에서 현재까지 확인한 최단횟수를 비교 해줍시다. 

if(visit[move_y][move_x]<=count && visit[move_y][move_x]!=0){//지나온곳;
        return;
    }
    else{ // 새로운길!
        visit[now_y][now_x]=count;
        for(int i=0;i<4;i++){
            dfs(move_y,move_x,i,count+1);
        }
    }

여기까지가 끝!

 

틀 부분에서 인덱스 체크 잘못해줘서 헤맸네요....

 

 

 

ALL

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

int dy[4]={1,-1,0,0};
int dx[4]={0,0,-1,1};// 하상좌우

int visit[102][102]={0,};  // 1~n까지 사용할것
int start[2];
int target[2];
int answer = 987654321;


void dfs(int now_y,int now_x,int dir,int count){ // 좌표와 방향
    if(now_y==target[0]&& now_x==target[1]){
        answer=min(answer,count-1);
        return;
    }
   
    if(answer<=count || visit[now_y][now_x]==-1){
        return;
    }
    
    int move_y=now_y;
    int move_x=now_x;
    
    while(1){  /// 쭉 보내기
        move_y+=dy[dir];
        move_x+=dx[dir];
        if(visit[move_y][move_x]==-1){//길막힘 
            move_y-=dy[dir];
            move_x-=dx[dir];//멈추기
            break;
        }
    }
   
    if(visit[move_y][move_x]<=count && visit[move_y][move_x]!=0){//지나온곳;
        return;
    }
    else{ // 새로운길!
        visit[now_y][now_x]=count;
        for(int i=0;i<4;i++){
            dfs(move_y,move_x,i,count+1);
        }
    }
    return;
}

int solution(vector<string> board) {
    
    for(int i=0;i<board.size()+2;i++){  // 처리
        for(int j=0;j<board[0].size()+2;j++){
            if(i==0 || j==0 || i==board.size()+1 || j==board[0].size()+1){
                visit[i][j]=-1;
            }
            else{
                if(board[i-1][j-1]=='D'){
                    visit[i][j]=-1;
                }
                else if(board[i-1][j-1]=='R'){
                    
                    start[0]=i;
                    start[1]=j;
                }
                else if(board[i-1][j-1]=='G'){
                    target[0]=i;
                    target[1]=j;
                }
            }
        }
    }
    
    
    /// 이제 이동 ㅇㅇ
    
    
    for(int i=0;i<4;i++){
        dfs(start[0],start[1],i,1);
    }
    
    if(answer==987654321){
        return -1;
    }
    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!