리코쳇 로봇

프로그래머스 - 리코쳇 로봇

문제

---

• 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임
• 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 친다.
• ↓ 보드게임판을 나타낸 예시
  ...D..R
  .D.G...
  ....D.D
  D....D.
  ..D....
  → "."은 빈 공간, "R"은 로봇의 처음 위치, "D"는 장애물의 위치, "G"는 목표지점이다.
  → "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈출 수 있다.
• 말이 목표위치에 도달하는데 최소 이동 횟수 return, 만약 목표위치에 도달할 수 없다면 -1 return

💡Idea

1. 장애물이나 맨 끝에 부딪힐 때까지 이동을 어떻게 할까?
   • 상하좌우 순서대로 한 방향으로 계속 이동하자
     → 장애물이나 맨 끝에 부딪혔다면 반복을 멈춤
2. 말이 목표위치에 도달할 수 없는지 어떻게 알까?
   • 한 번 방문했던 곳을 또 방문하게 된다면 도달할 수 없다고 판단하자

[ SourceCode ]

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

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

int solution(vector<string> board) {
    queue <pair<int, int>> tmp;
    int visit[100][100]; // 방문 시간
    fill(&visit[0][0], &visit[100][0], -1);
   
    for(int i=0; i<board.size(); i++) {
        for(int j=0; j<board[0].size(); j++) {
            if(board[i][j] == 'R') {
                tmp.push({i, j});
                visit[i][j] = 0;
            }
        }
    }
   
    while(!tmp.empty()) {
        int x = tmp.front().first;
        int y = tmp.front().second;
        tmp.pop();
       
        for(int i=0; i<4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
           
            while(1) {
                if(nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size()) break;
                if(board[nx][ny] == 'D') break; // 장애물이 있다면
                nx += dir[i][0];
                ny += dir[i][1];
            }
           
            nx -= dir[i][0];
            ny -= dir[i][1];
            if(board[nx][ny] == 'G') return visit[x][y] + 1;
            if(visit[nx][ny] > -1) continue;
            visit[nx][ny] = visit[x][y] + 1;
            tmp.push({nx, ny});
        }
    }
   
    return -1;
}

Feedback

---

1. 한 방향으로 계속 이동하는 방법을 오래 고민했었음.
   → 다음에 이런 유형의 문제가 나오면 풀 수 있을 것 같다 !