프로그래머스 - 리코쳇 로봇 [C++]

이 문제는 재귀를 이용해서 풀었다.

 

이 문제에서 핵심은 상하좌우로 이동할 때 장애물 또는 벽에 부딪힐 때까지 움직인 것을 한 번의 움직임으로 치는 걸 구현하는 것이다. 백준 삼성 SW 역량 테스트 기출 중에 판을 기울여서 구슬 두 개 빼는 문제가 있는데 그와 같은 방식이다.

 

또한 어떤 점을 도달했을 때 그 점을 처음 도달했다고 해서 반드시 최단 횟수로 도착한 것이 아니라는 점도 굉장히 중요하다. 따라서 visited 배열을 단순히 bool 로 선언하여 true면 재귀 호출하지 않는 방식으로 구현하면 테스트 케이스 1번이 7이 아닌 9가 나오게 된다.

 

이 때 약간의 다익스트라 알고리즘 개념을 사용했는데, 다익스트라에서는 거리 배열에 이미 유효한 값이 저장되어 있더라도 지금 경로의 비용이 더 작으면 값을 바꾸고 큐에 삽입한다. 이를 이용하여 visited에 이미 값이 저장되어 있더라도 지금이 더 짧으면 수정 후 호출하도록 로직을 구성하여 정답을 맞출 수 있었다.

 

#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
#define IMPOSSIBLE 1000000000
#define MAX 100

int maxY, maxX;
char matrix[MAX][MAX];
int visited[MAX][MAX];

bool inRange(int y, int x) {
    if (0 <= y && y < maxY && 
        0 <= x && x < maxX) {
        return true;
    }
    return false;
}

bool stuck(int y, int x) {
    if (matrix[y][x] == 'D') {
        return true;
    }
    return false;
}

pair<int, int> move(int y, int x, int direction) {
    switch (direction) {
        case UP:
            while (true) {
                y--;
                if (!inRange(y, x)) {
                    y++;
                    break;
                }
                if (stuck(y, x)) {
                    y++;
                    break;
                }
            }
            break;
        case DOWN:
            while (true) {
                y++;
                if (!inRange(y, x)) {
                    y--;
                    break;
                }
                if (stuck(y, x)) {
                    y--;
                    break;
                }
            }
            break;
        case LEFT:
            while (true) {
                x--;
                if (!inRange(y, x)) {
                    x++;
                    break;
                }
                if (stuck(y, x)) {
                    x++;
                    break;
                }
            }
            break;
        case RIGHT:
            while (true) {
                x++;
                if (!inRange(y, x)) {
                    x--;
                    break;
                }
                if (stuck(y, x)) {
                    x--;
                    break;
                }
            }
            break;
    }
    
    return {y, x};
}

pair<int, int> findStart() {
    for (int y = 0; y < maxY; y++) {
        for (int x = 0; x < maxX; x++) {
            if (matrix[y][x] == 'R') {
                return {y, x};
            }
        }
    }
    
    return {-1, -1};
}

int solve(int y, int x, int cnt) {
    int result = IMPOSSIBLE;
    
    if (matrix[y][x] == 'G') {
        return cnt;
    }
    
    for (int i = 0; i < 4; i++) {
        pair<int, int> next = move(y, x, i);
        int ny = next.first;
        int nx = next.second;
        
        if (visited[ny][nx] > cnt + 1) {
            visited[ny][nx] = cnt + 1;
            result = min(result, solve(ny, nx, cnt + 1));
        }
    }
    
    return result;
}

void makeMatrix(vector<string>& board) {
    for (int y = 0; y < maxY; y++) {
        for (int x = 0; x < maxX; x++) {
            matrix[y][x] = board[y][x];
        }
    }
}

void initVisited() {
    for (int y = 0; y < maxY; y++) {
        for (int x = 0; x < maxX; x++) {
            visited[y][x] = IMPOSSIBLE;
        }
    }
}

int solution(vector<string> board) {
    int answer = 0;
    
    maxY = board.size();
    maxX = board[0].size();
    makeMatrix(board);
    
    initVisited();
    
    pair<int, int> start = findStart();
    
    answer = solve(start.first, start.second, 0);
    
    if (answer == IMPOSSIBLE) {
        return -1;
    }
    
    return answer;
}