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

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

---

 

해결전략

 

너비우선탐색 BFS

---

 

정답코드

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int INTMAX = 99999;

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int solution(vector<string> v) {
    int r = v.size();
    int c = v[0].size();

    queue<pair<int, int>> Q;
    vector<vector<int>> ch(r, vector<int>(c, INTMAX)); // 각 위치까지의 최단 거리를 저장하는 2차원 벡터. 최대값으로 초기화

    int goalY, goalX;

	for(int y = 0; y < r; y++){
        for (int x = 0; x < c; x++) {
            if(v[y][x] == 'R'){ // 출발 지점
                Q.push({ y, x });
                ch[y][x] = 0; // 출발지점 최단거리는 0
            }
            else if(v[y][x] == 'G'){ // 도착 지점
                goalY = y;
                goalX = x;
            }
        }
    }
    
    while(!Q.empty()){
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();

        for(int i = 0; i < 4; i++){
            int ny = y + dirY[i];
            int nx = x + dirX[i];

            // 범위를 벗어나거나 벽('D')이 있는 경우 이동하지 않는다
            if (ny < 0 || r <= ny || nx < 0 || c <= nx || v[ny][nx] == 'D') continue;

            // 같은 방향으로 계속 이동
            int nny = y;
            int nnx = x;
            while(true)
            {
                nny += dirY[i];
                nnx += dirX[i];

                // 범위를 벗어나거나 벽('D')이 있는 곳에 도착하면 이동을 멈추고 한 칸 뒤로 돌아간다.
                if (nny < 0 || r <= nny || nnx < 0 || c <= nnx || v[nny][nnx] == 'D'){
                    nny -= dirY[i];
                    nnx -= dirX[i];

                    // 방문한 위치까지의 거리가 기존보다 짧으면 거리를 갱신하고, 방문할 위치를 큐에 추가
                    if(ch[nny][nnx] > ch[y][x] + 1){
                        Q.push({ nny, nnx });
                        ch[nny][nnx] = ch[y][x] + 1;
                    }
                    break;
                }
            }
        }
    }
    
    // 도착지점의 최단거리가 최대값에서 변경된적이 없다면 -1, 있다면 해당 최단거리 값을 answer에 담음
    int answer = ch[goalY][goalX] == INTMAX ? -1 : ch[goalY][goalX];

    return answer;
}

int main()
{
    vector<string> testcase1 = { "...D..R", ".D.G...", "....D.D", "D....D.", "..D...." };
    vector<string> testcase2 = { ".D.R", "....", ".G..", "...D" };
    cout << solution(testcase1) << "\n"; // answer = 7
    cout << solution(testcase2) << "\n"; // answer = -1

    return 0;
}

 

 

아래는 ch 2차원 배열의 출력값 + answer 출력값

 

---