[Programmers] Lv2. 리코쳇 로봇 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

처음에는 DFS로 접근을 했다가 결국 못 풀었습니다. 아마 그대로 진행했어도 가지 치기를 못해서 시간 초과가 났을 것 같네요. 그래서 BFS로 전략을 바꿔 풀다 보니 알게 된 사실인데, 제가 설계를 조금 잘못했었더라구요. 장애물이나 맨 끝에 부딪힌 빈 공간만 방문 표시를 했었어야 했는데, 지나간 경로를 다 방문 표시 해버렸습니다..ㅎㅎㅎ

 

아무튼, BFS를 통한 전략은 다음과 같습니다.

 

1. 로봇의 처음 위치 'R', 목표 지점 'G'의 좌표를 알아낸 후 저장해둔다.
2. R의 좌표를 방문 처리한 후, 큐(Queue)에 삽입한다.
3. 큐가 빌 때까지,
   • 큐에서 하나 가져와, 현재 좌표가 목표 지점인지 검사한다.
     • 목표 지점이라면, min(이전 탐색값, 현재 탐색값)을 진행한다.
   • 상, 하, 좌, 우를 차례대로 탐색한다.
     • 장애물이나 맨 끝 벽이 아니라면 계속 해당 방향으로 진행한다.
     • 장애물이나 맨 끝 벽에 막히고, 이전에 방문한 좌표가 아닐 경우, 큐에 현재 좌표를 삽입한다.
     • 현재 좌표를 방문 처리한다.

 

✏️소스 코드 및 결과

#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int MAX_INT = 2147483647;
vector<pair<int, int>> directions {{-1, 0}, { 1, 0 }, { 0, -1 }, { 0, 1 }};   // 상, 하, 좌, 우

struct Info
{
    Info(int row, int col, int currentMoveCount) : _row(row), _col(col), _currentMoveCount(currentMoveCount) { }
    int _row;
    int _col;
    int _currentMoveCount;
};


int FindShortestDistance(const vector<string>& board, pair<int, int> current, const pair<int, int>& end) {
    int minCount = MAX_INT;

    queue<Info> myQueue;
    vector<vector<bool>> visited(board.size(), vector<bool>(board[0].length(), false));
    
    myQueue.push(Info(current.first, current.second, 0));
    visited[current.first][current.second] = true;


    while (!myQueue.empty()) {
        Info current = myQueue.front();
        myQueue.pop();
        bool isArrivalGoal = (current._row == end.first) and (current._col == end.second);

        if (isArrivalGoal)
            minCount = min(minCount, current._currentMoveCount);


        for (int i = 0; i < directions.size(); i++) {

            int nextRow = current._row + directions[i].first;
            int nextCol = current._col + directions[i].second;
            bool isBlocked = nextRow < 0 or nextRow >= board.size() or nextCol < 0 or nextCol >= board[0].length() or board[nextRow][nextCol] == 'D';

            if (isBlocked)
                continue;

            int tempNextRow = nextRow;
            int tempNextCol = nextCol;

            while (true) {
                tempNextRow += directions[i].first;
                tempNextCol += directions[i].second;
                isBlocked = tempNextRow < 0 or tempNextRow >= board.size() or tempNextCol < 0 or tempNextCol >= board[0].length() or board[tempNextRow][tempNextCol] == 'D';

                if (isBlocked)
                    break;
                nextRow += directions[i].first;
                nextCol += directions[i].second;
            }

            if (visited[nextRow][nextCol])
                continue;
            
            myQueue.push(Info(nextRow, nextCol, current._currentMoveCount + 1));
            visited[nextRow][nextCol] = true;
        }
    }

    return minCount;
}


int FindMinMovingCount(const vector<string>& board, map<char, pair<int, int>> symbolPositions) {
    auto currentRobotPosition = symbolPositions['R'];
    auto goal = symbolPositions['G'];

    int answer = FindShortestDistance(board, currentRobotPosition, goal);
    return answer == MAX_INT ? -1 : answer;
}

map<char, pair<int, int>> GetPositions(const vector<string>& board) {
    map<char, pair<int, int>> results;

    for (int row = 0; row < board.size(); row++) {
        for (int col = 0; col < board[row].length(); col++) {
            char symbol = '@';

            if (board[row][col] == 'R')
                symbol = 'R';
            else if (board[row][col] == 'G')
                symbol = 'G';

            if (symbol != '@')
                results.insert(make_pair(symbol, make_pair(row, col)));
        }
    }

    return results;
}


int solution(vector<string> board) {
    map<char, pair<int, int>> symbolPositions = GetPositions(board);
    int answer = FindMinMovingCount(board, symbolPositions);

    return answer;
}

 

제출 결과